List-colouring squares of sparse subcubic graphs

Zdeněk Dvořák

Charles University, Prague

Colouring the square of a graph naturally arises in connection with the distance labelings, which have been studied intensively. We consider the problem for sparse subcubic graphs. We show that the choosability $\chi_\ell(G^2)$ of the square of a subcubic graph $G$ of maximum average degree $d$ is at most four if $d<24/11$ and $G$ does not contain a 5-cycle, $\chi_\ell(G^2)$ is at most five if $d<7/3$ and $\chi_\ell(G^2)$ at most six if $d<5/2$. Wegner's conjectures claims that the chromatic number of the square of a subcubic planar graph is at most seven. Our result implies that $\chi_\ell(G^2)$ is at most four if $g\ge 24$, it is at most $5$ if $g\ge 14$ and it is at most $6$ if $g\ge 10$. For lower bounds, we find a planar subcubic graph $G_1$ of girth $9$ such that $\chi(G_1^2)=5$ and a planar subcubic graph $G_2$ of girth five such that $\chi(G_2^2)=6$. As a consequence, we show that the problem of $4$-colouring of the square of a subcubic planar graph of girth $g=9$ is NP-complete.