# Coloring the square of a sparse graph $G$ with almost $\Delta(G)$ colors

Research paper by **Matthew Yancey**

Indexed on: **13 Apr '15**Published on: **13 Apr '15**Published in: **Mathematics - Combinatorics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### 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$.