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

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\ne y$ and $d_G(x,y)\le 2$. Bonamy, Lévêque, and Pinlou conjectured that if $mad(G)<4-\frac{2}{c+1}$ and $\Delta (G)$ is large, then ${\chi }_{\ell }(G^2)\le \Delta (G)+c$. We prove that if $c\ge 3$, $mad(G)<4-\frac{4}{c+1}$, and $\Delta (G)$ is large, then ${\chi }_{\ell }(G^2)\le \Delta (G)+c$. Dvořák, Krá\soft{l}, Nejedlý, and Škrekovski conjectured that $\chi (G^2)\le \Delta (G)+2$ when $\Delta (G)$ is large and $G$ is planar with girth at least $5$; our result implies $\chi (G^2)\le \Delta (G)+6$.