Article
5-choosability of graphs with crossings far apart
Journal of Combinatorial Theory, Series B
Document Type
Article
Disciplines
Publication Version
Submitted Manuscript
Publication Date
3-1-2017
DOI
10.1016/j.jctb.2016.11.004
Abstract
We give a new proof of the fact that every planar graph is 5-choosable, and use it to show that every graph drawn in the plane so that the distance between every pair of crossings is at least 15 is 5-choosable. At the same time we may allow some vertices to have lists of size four only, as long as they are far apart and far from the crossings.
Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Copyright Owner
Elsevier Inc.
Copyright Date
2016
Language
en
File Format
application/pdf
Citation Information
Zdeněk Dvořák, Bernard Lidicky and Bojan Mohar. "5-choosability of graphs with crossings far apart" Journal of Combinatorial Theory, Series B Vol. 123 (2017) p. 54 - 96 Available at: http://works.bepress.com/bernard-lidicky/32/
This is a manuscript of an article published as Dvořák, Zdeněk, Bernard Lidický, and Bojan Mohar. "5-choosability of graphs with crossings far apart." Journal of Combinatorial Theory, Series B 123 (2017): 54-96. doi: 10.1016/j.jctb.2016.11.004. Posted with permission.