Strong edge-colorings of sparse graphs with large maximum degree
read the original abstract
A {\em strong $k$-edge-coloring} of a graph $G$ is a mapping from $E(G)$ to $\{1,2,\ldots,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'(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'(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 ${\rm 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 ${\rm Mad}(G)< 8/3$ and $\Delta(G)\geq 9$, then $\chi_s'(G)\leq 3\Delta(G) -3$ (the bound $3\Delta(G) -3$ is sharp) and if ${\rm Mad}(G)<3$ and $\Delta(G)\geq 7$, then $\chi_s'(G)\leq 3\Delta(G)$ (the restriction ${\rm Mad}(G)<3$ is sharp).
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Coloring, List Coloring, and Painting Squares of Graphs (and other related problems)
This is a survey compiling results on strong edge-coloring and related coloring problems for squares of graphs in planar and sparse classes.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.