Coloring the square of a sparse graph G with almost Delta(G) colors
read the original abstract
For a graph $G$, let $G^2$ be the graph with the same vertex set as $G$ and $xy \in E(G^2)$ when $x \neq y$ and $d_G(x,y) \leq 2$. Bonamy, L\'ev\^{e}que, and Pinlou conjectured that if $mad (G) < 4 - \frac{2}{c+1}$ and $\Delta(G)$ is large, then $\chi_\ell(G^2) \leq \Delta(G) + c$. We prove that if $c \geq 3$, $mad (G) < 4 - \frac{4}{c+1}$, and $\Delta(G)$ is large, then $\chi_\ell(G^2) \leq \Delta(G) + c$. Dvo\v{r}\'ak, Kr\'{a}\soft{l}, Nejedl\'{y}, and \v{S}krekovski conjectured that $\chi(G^2) \leq \Delta(G) +2$ when $\Delta(G)$ is large and $G$ is planar with girth at least $5$; our result implies $\chi (G^2) \leq \Delta(G) +6$.
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.