Strong chromatic index of k-degenerate graphs

Abstract

A {\em strong edge coloring} of a graph $G$ is a proper edge coloring in which every color class is an induced matching. The {\em strong chromatic index} $\chiup_{s}'(G)$ of a graph $G$ is the minimum number of colors in a strong edge coloring of $G$. In this note, we improve a result by D{\k e}bski \etal [Strong chromatic index of sparse graphs, arXiv:1301.1992v1] and show that the strong chromatic index of a $k$-degenerate graph $G$ is at most $(4k-2)\cdot \Delta (G)-2k^2+1$. As a direct consequence, the strong chromatic index of a $2$-degenerate graph $G$ is at most $6\Delta (G)-7$, which improves the upper bound $10\Delta (G)-10$ by Chang and Narayanan [Strong chromatic index of 2-degenerate graphs, J. Graph Theory 73 (2013) (2) 119--126]. For a special subclass of $2$-degenerate graphs, we obtain a better upper bound, namely if $G$ is a graph such that all of its $3^{+}$-vertices induce a forest, then $\chiup_{s}'(G) \leq 4 Δ(G) -3$; as a corollary, every minimally $2$-connected graph $G$ has strong chromatic index at most $4\Delta (G)-3$. Moreover, all the results in this note are best possible in some sense.

3 pages in Discrete Mathematics, 2015

References in corpus (3)

• A note on strong edge-colorings of 2-degenerate graphs
• Strong edge-colorings for k-degenerate graphs
• Strong chromatic index of chordless graphs

Cited by in corpus (1)

• Strong edge-colorings of sparse graphs with large maximum degree