DOIAbstract
AbstractFor 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 Discrete Math. 281 (2004) 129, Austral. J. Combin. 10 (1994) 97, Austral. J. Combin. 18 (1998) 219 and Combin. Probab. Comput. 11 (1) (2002) 103. 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 |U|=|V|⩾n0(d,ε) satisfy χs(G)⩽ζ(ε)Δ(G)2, where ζ(ε)→0 as ε→0 (this order of magnitude is easily se...
Add to ORKG