Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777657 | Journal of Combinatorial Theory, Series B | 2017 | 42 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
ZdenÄk DvoÅák, Bernard Lidický, Bojan Mohar, Luke Postle,