Degeneracy and Colorings of Squares of Planar Graphs without 4-Cycles

We prove several results on coloring squares of planar graphs without 4-cycles. First, we show that ifGis such a graph, thenG(2)is (Delta(G) + 72)-degenerate. This implies an upper bound of Delta(G) divide 73 on the chromatic number ofG(2)as well as on several variants of the chromatic number such as the list-chromatic number, paint number, Alon-Tarsi number, and correspondence chromatic number. We also show that if Delta(G) is sufficiently large, then the upper bounds on each of these parameters ofG(2)can all be lowered to Delta(G) + 2 (which is best possible). To complement these results, we show that 4-cycles are unique in having this property. Specifically, let S be a finite list of positive integers, with 4 is not an element of S. For each constantC, we construct a planar graphG(s,c)with no cycle with length inS, but for which chi(GS,C2) >Delta(G(s,c)) +C.