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

Marthe Bonamy, Daniel W. Cranston, Luke Postle

Published 2015-08-14Version 1

We prove a conjecture of Dvo\v{r}\'ak, Kr\'al, Nejedl\'y, and \v{S}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.