Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331912 | Information Processing Letters | 2015 | 5 Pages |
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
MichaÅ DÄbski, JarosÅaw Grytczuk, MaÅgorzata ÅleszyÅska-Nowak,