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 2 k. 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 4 kΔ-2 k in the square of the line graph of G, implying that χ'_s(G) ≤ 4 kΔ-2 k + 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(4 k-1)Δ-2 k in the square of the line graph of G, implying that χ'_s(G) ≤(4 k-1)Δ-2 k + 1.