The strong chromatic index of a class of graphs |
| |
Authors: | Jianzhuan Wu |
| |
Institution: | Department of Mathematics, Southeast University, Nanjing 210096, PR China |
| |
Abstract: | The strong chromatic index of a graph G is the minimum integer k such that the edge set of G can be partitioned into k 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 G is bipartite and if for each edge xy∈E(G), d(x)+d(y)≤5, then sχ′(G)≤6. Let H0 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 G (not necessarily bipartite) is not isomorphic to H0 and d(x)+d(y)≤5 for any edge xy of G then sχ′(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. |
| |
Keywords: | Strong edge coloring Strong chromatic index Induced matching Line graph |
本文献已被 ScienceDirect 等数据库收录! |
|