Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903882 | Journal of Combinatorial Theory, Series B | 2018 | 17 Pages |
Abstract
We introduce a new variant of graph coloring called correspondence coloring which generalizes list coloring and allows for reductions previously only possible for ordinary coloring. Using this tool, we prove that excluding cycles of lengths 4 to 8 is sufficient to guarantee 3-choosability of a planar graph, thus answering a question of Borodin.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
ZdenÄk DvoÅák, Luke Postle,