A Note on Strong Edge Coloring of Sparse Graphs

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.