The strong chromatic index of a class of graphs

Abstract: The strong chromatic index of a graph is the minimum integer such that the edge set of can be partitioned into 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 is bipartite and if for each edge , , then . Let 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 (not necessarily bipartite) is not isomorphic to and for any edge of then . The proof of the result implies a linear time algorithm to produce a strong edge coloring using at most 6 colors for such graphs. [Copyright &y& Elsevier]