Article ID Journal Published Year Pages File Type
10331912 Information Processing Letters 2015 5 Pages PDF
Abstract
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 χs′(G), is the least possible number of colors in a strong edge coloring of G. In this note, we prove that χs′(G)≤(4k−1)Δ(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 χs′(G)≤4Δ−3 for any chordless graph G. Both bounds remain valid for the list version of the strong edge coloring of these graphs.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,