Let $G$ be a planar graph without 4-cycles and 5-cycles and with maximum degree $\Delta\ge 32$. We prove that $\chi_{ \ell}(G^2)\le \Delta+3$. For arbitrarily large maximum degree $\Delta$, there exist planar graphs $G_{ \Delta}$ of girth 6 with $\chi(G_{ \Delta}^2)=\Delta+2$. Thus, our bound is within 1 of being optimal. Further, our bound comes from coloring greedily in a good order, so the bound immediately extends to online list-coloring. In addition, we prove bounds for $L(p,q)$-labeling. Specifically, $\lambda_{ 2,1}(G)\le \Delta+8$ and, more generally, $\lambda_{ p,q}(G)\le (2q-1)\Delta+6p-2q-2$, for positive integers $p$ and $q$ with $p\ge q$. Again, these bounds come from a greedy coloring, so they immediately extend to the list-coloring and online list-coloring variants of this problem.
Categories: math.CO