Planar Graphs of Girth at least Five are Square $(\Delta +2)$-Choosable

Abstract

We prove a conjecture of Dvořák, Král, Nejedlý, and Škrekovski that planar graphs of girth at least five are square $(\Delta +2)$-colorable for large enough $\Delta$. In fact, we prove the stronger statement that such graphs are square $(\Delta +2)$-choosable and even square $(\Delta +2)$-paintable.

22 pages, 7 figures; this version incorporates reviewer feedback: fixed and rewrote proof of Lemma 3.5, expanded Section 4; to appear in J. Combin. Theory Ser. B