Bounding the strong chromatic index of dense random graphs Original Research Article

For a graph 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. Palka (Austral. J. Combin. 18 (1998) 219–226), proved that if p=p(n)=Θ(n−1), then with high probability, χs(G(n,p))=O(Δ(G(n,p))). Recently Vu (Combin. Probab. Comput. 11 (2002) 103–111), proved that if n−1(ln n)1+δ⩽p=p(n)⩽n−ε for any 0<ε, δ<1, then with high probability, χs(G(n,p))=O((pn)2/ln(pn)). In this note, we prove that if p=p(n)>n−ε for all ε>0, then with b=(1−p)−1, with high probability, (1−o(1))(pn2/logb n)⩽χs(G(n,p))⩽(2+o(1))(pn2/logb n).