Skip to main content
Article
5-List-Coloring Planar Graphs with Distant Precolored Vertices
Journal of Combinatorial Theory, Series B
  • Zdeněk Dvořák, Charles University
  • Bernard Lidicky, Iowa State University
  • Bojan Mohar, Simon Fraser University
  • Luke Postle, University of Waterloo
Document Type
Article
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

Comments

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.

Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Copyright Owner
Elsevier Inc.
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/