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

Ilkyoo Choi, Daniel W. Cranston, Théo Pierron

We prove several results on coloring squares of planar graphs without 4-cycles. First, we show that if $G$ is such a graph, then $G^2$ is $(\Delta (G)+72)$-degenerate. This implies an up…