Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8

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.

22 pages, 3 figures; v2: improves presentation