Abstract
The problem of coloring the square of a graph naturally arises in connection with the distance labelings, which have been studied intensively. We consider this 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 [.lt.] 24/11$ and $G$ does not contain a 5-cycle, at most five if $d [.lt.] 7/3$, and at most six if $d [.lt.] 5/2$. Wegner's conjecture claims that the chromatic number of the square of a subcubic planar graph is at most seven.
Let $G$ be a planar subcubic graph of girth $g$. Our result implies that $\chi_\ell(G^2)$ is at most four if $g\ge 24$, at most $5$ if $g\ge 14$, and 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 5 such that $\chi(G_2^2)=6$.