Strong Edge Colorings of Uniform Graphs

For a graph G = (V (G); E(G)), a strong edge coloring of G is an edge coloring in which every color class is an induced matching. The strong chromatic index of G, s(G), is the smallest number of colors in a strong edge coloring of G. The strong chromatic index of the random graph G(n; p) was considered in [2], [3], [11], and [14]. In this paper, we consider s(G) for a related class of graphs G known as uniform or -regular graphs. In particular, we prove that for 0 < d < 1, all (d; )-regular bipartite graphs G = (U [ V;E) with jU j = jV j n0(d; ) satisfy s(G) ()(G) 2, where () ! 0 as ! 0 (this order of magnitude is easily seen to be best possible). Our main tool in proving this statement is a powerful packing result of Pippenger and Spencer [10]. Key words: Strong chromatic index, the regularity lemma