Labeling Planar Graphs without 4,5-Cycles with a Condition on Distance Two
Haiyang Zhu, Xinzhong Lü, Cui-Qi Wang, Ming Chen · SIAM Journal on Discrete Mathematics · 2012
Wegner conjectured that for each planar graph G with maximum degree $\Delta$ at least 4, $\chi(G^2)\leq\Delta+5$ if $4\leq\Delta\leq7$, and $\chi(G^2)\leq\lfloor \frac{3\Delta}{2}\rfloor +1$ if $\Delta\geq8$. Let G be a planar graph without 4- and 5-cycles. In this paper, we discuss the $L(p,q)$-labeling of G and show that $\lambda_{p,q}(G)\leq(2q-1)\Delta+6p+6q-6$ and $\lambda_{p,q}(G)\leq\max\{(2q-1)\Delta+6p+2q-4,9(2q-1)+8p-4,6(2q-1)+10p-5\},$ where p and q are positive integers with $p\geq q$. As a corollary, $\chi(G^2)\leq\Delta+7$ if $\Delta\leq7$, $\chi(G^2)\leq14$ if $\Delta=8$, and $\chi(G^2)\leq\Delta+5$ if $\Delta\geq9$.