Campus Units

Mathematics

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

1-2017

Journal or Book Title

Journal of Combinatorial Theory

Volume

122

First Page

311

Last Page

352

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. 10.1016/j.jctb.2016.06.006

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Copyright Owner

Elsevier Inc.

Language

en

File Format

application/pdf

Published Version

Share

COinS