Back to Search Start Over

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

Authors :
Bonamy, Marthe
Cranston, Daniel W.
Postle, Luke
Source :
Journal of Combinatorial Theory, Series B. Vol. 134, 2019, pp. 218-238
Publication Year :
2015

Abstract

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.<br />Comment: 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

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Journal :
Journal of Combinatorial Theory, Series B. Vol. 134, 2019, pp. 218-238
Publication Type :
Report
Accession number :
edsarx.1508.03663
Document Type :
Working Paper