Strong edge-colorings of sparse graphs with large maximum degree

Abstract

A {\em strong $k$-edge-coloring} of a graph $G$ is a mapping from $E(G)$ to $\{1,2,\dots ,k\}$ such that every two adjacent edges or two edges adjacent to the same edge receive distinct colors. The {\em strong chromatic index} ${\chi }_s^{\prime }(G)$ of a graph $G$ is the smallest integer $k$ such that $G$ admits a strong $k$-edge-coloring. We give bounds on ${\chi }_s^{\prime }(G)$ in terms of the maximum degree $\Delta (G)$ of a graph $G$. when $G$ is sparse, namely, when $G$ is $2$-degenerate or when the maximum average degree $\mathrm{Mad}(G)$ is small. We prove that the strong chromatic index of each $2$-degenerate graph $G$ is at most $5\Delta (G)+1$. Furthermore, we show that for a graph $G$, if $\mathrm{Mad}(G)<8/3$ and $\Delta (G)\ge 9$, then ${\chi }_s^{\prime }(G)\le 3\Delta (G)-3$ (the bound $3\Delta (G)-3$ is sharp) and if $\mathrm{Mad}(G)<3$ and $\Delta (G)\ge 7$, then ${\chi }_s^{\prime }(G)\le 3\Delta (G)$ (the restriction $\mathrm{Mad}(G)<3$ is sharp).

References in corpus (1)

• Strong edge-colorings for k-degenerate graphs

Cited by in corpus (1)

• Semistrong edge colorings of planar graphs