The strong chromatic index of sparse graphs

A coloring of the edges of a graph G is strong if each color class is an induced matching of G. The strong chromatic index of G, denoted by chi'(s)(G), is the least possible number of colors in a strong edge coloring of G. In this note, we prove that chi'(s)(G) <= (4k - 1)Delta(G) - k(2k + 1) + 1 for every k-degenerate graph G. This confirms the strong version of a conjecture stated recently by Chang and Narayanan [4]. Our approach also allows to improve the upper bound from [4] for chordless graphs. We get that chi'(s)(G) <= 4 Delta - 3 for any chordless graph G. Both bounds remain valid for the list version of the strong edge coloring of these graphs. (C) 2014 Elsevier B.V. All rights reserved.