Abstract
A strong edge coloring of a graph is a proper edge coloring where the edges at distance at most 2 receive distinct colors. The strong chromatic index χ′s(G) of a graph G is the minimum number of colors used in a strong edge coloring of G. In an ordering Q of the vertices of G, the back degree of a vertex x of G in Q is the number of vertices adjacent to x, each of which has smaller index than x in Q. Let G be a graph of maximum degree Δ and maximum average degree at most 2k. Yang and Zhu [J. Graph Theory, 83, 334–339 (2016)] presented an algorithm that produces an ordering of the edges of G in which each edge has back degree at most 4kΔ − 2k in the square of the line graph of G, implying that χ′s(G) ≤ 4kΔ − 2k + 1. In this note, we improve the algorithm of Yang and Zhu by introducing a new procedure dealing with local structures. Our algorithm generates an ordering of the edges of G in which each edge has back degree at most (4k − 1)Δ − 2k in the square of the line graph of G, implying that χ′s(G) ≤ (4k − 1)Δ − 2k + 1.
Similar content being viewed by others
References
Andersen, L. D.: The strong chromatic index of a cubic graph is at most 10. Discrete Math., 108, 231–252 (1992)
Bondy, J. A., Murty, U. S. R.: Graph Theory, Springer, 2008
Chang, G. J., Narayanan, N.: Strong chromatic index of 2-degenerate graphs. J. Graph Theory, 73(2), 119–126 (2013)
Cranston, D.: Strong edge-coloring graphs with maximum degree 4 using 22 colors. Discrerte Math., 306, 2772–2778 (2006)
Dębski, M., Grytczuk, J., Śleszyńska-Nowak, M.: The strong chromatic index of sparse graphs. Inform. Process. Lett., 115(2), 326–330 (2015)
Erdős, P.: Problems and results in combinatorial analysis and graph theory. Discrete Math., 72(1–3), 81–92 (1988)
Fouquet, J. L., Jolivet, J.: Strong edge-coloring of graphs and applications to multi-k-gons. Ars Combin., 16A, 141–150 (1983)
Fouquet, J. L., Jolivet, J.: Strong edge-coloring of cubic planar graphs. Progress in Graph Theory, 247–264 (1984) (Waterloo 1982)
Hakimi, S. L.: On the degree of the vertices of a directed graph. J. Franklin Inst., 279, 290–308 (1965)
Horák, P., Qing, H., Trotter, W. T.: Induced matchings in cubic graphs. J. Graph Theory, 17, 151–160 (1993)
Molloy, M., Reed, B.: A bound on the strong chromatic index of a graph. J. Combinatorial Theory B, 69, 103–109 (1997)
Wang, T.: Strong chromatic index of k-degenerate graphs. Discrete. Math., 330(6), 17–19 (2014)
Yang, D., Zhu, X.: Strong Chromatic Index of Sparse Graphs. J. Graph Theory, 83, 334–339 (2016)
Yu, G.: Strong edge-colorings for k-degenerate graphs. Graphs Combin., 31, 1815–1818 (2015)
Acknowledgements
We would like to thank referees for their comments and suggestions to improve this paper.
Author information
Authors and Affiliations
Corresponding authors
Additional information
The first author is supported by NSFC (Grant No. 11571180); the second author is partially supported by Natural Science Foundation of Jiangsu Province (Grant No. BK20170862) and NSFC (Grant Nos. 11701142, 11426085); the third author is partially supported by NSFC (Grant Nos. 11571180, 11331003 and 11426085)
Rights and permissions
About this article
Cite this article
Dong, W., Li, R. & Xu, B.G. A Note on Strong Edge Coloring of Sparse Graphs. Acta. Math. Sin.-English Ser. 35, 577–582 (2019). https://doi.org/10.1007/s10114-018-7186-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10114-018-7186-7