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

被引：143

作者：

Dvorak, Zdenek ^{[1
]}

Postle, Luke ^{[2
]}

机构：

[1] Charles Univ Prague, Prague, Czech Republic

[2] Univ Waterloo, Waterloo, ON, Canada

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2018年 / 129卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

Correspondence coloring; DP-coloring; List coloring; Planar graphs;

D O I：

10.1016/j.jctb.2017.09.001

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. (C) 2017 Elsevier Inc. All rights reserved.

引用

页码：38 / 54

页数：17

共 18 条

[1]

Alon N, 2000, RANDOM STRUCT ALGOR, V16, P364

[2] EVERY PLANAR MAP IS 4 COLORABLE .1. DISCHARGING [J].