List-Coloring the Squares of Planar Graphs without 4-Cycles and 5-Cycles

Let G be a planar graph without 4-cycles and 5-cycles and with maximum degree Delta >= 32. We prove that chi(e)(G(2)) <= 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) <= Delta + 8 and, more generally, lambda(p,q) (G) <= (2q - 1) Delta + 6p - 2q - 2, for positive integers p and q with p >= 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.(C) 2016 Wiley Periodicals, Inc.