Back to Search
Start Over
Planar Graphs of Girth at least Five are Square $(\Delta + 2)$-Choosable
- 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 :
- Mathematics - Combinatorics
Subjects
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