Speaker: Peter Bradshaw (UIUC)
Title: Strong edge-colorings of C4-free graphs
Abstract: A strong edge-coloring of a graph is an edge-coloring in which each color class gives an induced matching. Erdos and Nesetril conjectured that if G has maximum degree D, then G has a strong edge coloring with 1.25D^2 colors. In 2000, Mahdian proved that if G has no C_4 subgraph, then G in fact has a strong edge-coloring with (2+o(1)) D / log D colors. His main tool was an iterative random procedure, informally known as a "nibble."
In this talk, we show that a refinement of Mahdian's nibble method implies that every C_4-free graph of maximum degree D has a strong edge-coloring with (1+o(1)) D / log D colors, improving Mahdian's result by a factor of 2. We strongly believe that this upper bound is best achievable using a local random algorithm. Our refined nibble approach also gives insight into applications of the nibble method to other problems.
This talk is based on joint work with Richard Bi and Jingwei Xu.