Article
5-List-Coloring Planar Graphs with Distant Precolored Vertices
Journal of Combinatorial Theory, Series B
Document Type
Article
Disciplines
Publication Version
Accepted Manuscript
Publication Date
1-1-2017
DOI
10.1016/j.jctb.2016.06.006
Abstract
We answer positively the question of Albertson asking whether every planar graph can be 5-list-colored even if it contains precolored vertices, as long as they are sufficiently far apart from each other. In order to prove this claim, we also give bounds on the sizes of graphs critical with respect to 5-list coloring. In particular, if G is a planar graph, H is a connected subgraph of G and L is an assignment of lists of colors to the vertices of G such that |L(v)| ≥ 5 for every v ∈ V (G) \ V (H) and G is not L-colorable, then G contains a subgraph with O(|H| 2) vertices that is not L-colorable
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, Bojan Mohar and Luke Postle. "5-List-Coloring Planar Graphs with Distant Precolored Vertices" Journal of Combinatorial Theory, Series B Vol. 122 (2017) p. 311 - 352 Available at: http://works.bepress.com/bernard-lidicky/31/
This is a manuscript of an article published as Dvořák, Zdeněk, Bernard Lidický, Bojan Mohar, and Luke Postle. "5-list-coloring planar graphs with distant precolored vertices." Journal of Combinatorial Theory, Series B 122 (2017): 311-352. doi: 10.1016/j.jctb.2016.06.006. Posted with permission.