The strong chromatic index of a class of graphs

The strong chromatic index of a graph GG is the minimum integer kk such that the edge set of GG can be partitioned into kk induced matchings. Faudree et al. [R.J. Faudree, R.H. Schelp, A. Gyárfás, Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205–211] proposed an open problem: If GG is bipartite and if for each edge xy∈E(G)xy∈E(G), d(x)+d(y)≤5d(x)+d(y)≤5, then sχ′(G)≤6sχ′(G)≤6. Let H0H0 be the graph obtained from a 5-cycle by adding a new vertex and joining it to two nonadjacent vertices of the 5-cycle. In this paper, we show that if GG (not necessarily bipartite) is not isomorphic to H0H0 and d(x)+d(y)≤5d(x)+d(y)≤5 for any edge xyxy of GG then sχ′(G)≤6sχ′(G)≤6. The proof of the result implies a linear time algorithm to produce a strong edge coloring using at most 6 colors for such graphs.