Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
2018
Abstrakt
We introduce a new variant of graph coloring called correspondence colming 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.