Planar graphs of girth at least five are square (Δ+2)-choosable

被引：16

作者：

Bonamy, Marthe ^{[1
]}

Cranston, Daniel W. ^{[2
]}

Postle, Luke ^{[3
]}

机构：

[1] Univ Bordeaux, LaBRI, CNRS, Bordeaux, France

[2] Virgina Commonwealth Univ, Dept Math & Appl Math, Richmond, VA 23284 USA

[3] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2019年 / 134卷

基金：

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

关键词：

List-coloring; Choosability; Square; Planar graph; Girth; 5; Paintability;

D O I：

10.1016/j.jctb.2018.06.005

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove a conjecture of Dvorak, Kral, Nejedly, and Skrekovski that planar graphs of girth at least five with maximum degree A are square (Delta + 2)-colorable for large enough Delta. In fact, we prove the stronger statement that such graphs are square (Delta + 2)-choosable and even square (Delta + 2)-paintable. (C) 2018 Elsevier Inc. All rights reserved.

引用

页码：218 / 238

页数：21

共 12 条

[1] COLORINGS AND ORIENTATIONS OF GRAPHS
ALON, N
TARSI, M
[J]. COMBINATORICA, 1992, 12 (02) : 125 - 134
[2] List coloring the square of sparse graphs with large degree
Bonamy, Marthe
Leveque, Benjamin
Pinlou, Alexandre
[J]. EUROPEAN JOURNAL OF COMBINATORICS, 2014, 41 : 128 - 137
[3] Graphs with maximum degree Δ ≥ 17 and maximum average degree less than 3 are list 2-distance (Δ+2)-colorable
Bonamy, Marthe
Leveque, Benjamin
Pinlou, Alexandre
[J]. DISCRETE MATHEMATICS, 2014, 317 : 19 - 32
[4] 2-distance (Δ+2)-coloring of planar graphs with girth six and Δ ≥ 18
Borodin, O. V.
Ivanova, A. O.
[J]. DISCRETE MATHEMATICS, 2009, 309 (23-24) : 6496 - 6502
[5] Borodin O.V., 2004, Siberian Electronic Math. Reports, V1, P129
[6] List 2-distance (Δ+2)-coloring of planar graphs with girth six
Borodin, Oleg V.
Ivanova, Anna O.
[J]. EUROPEAN JOURNAL OF COMBINATORICS, 2009, 30 (05) : 1257 - 1262
[7] Charpentier C., 2014, 2 DISTANCE COLORING
[8] Choi I., 2018, PAINTING CORRES COLO
[9] Coloring squares of planar graphs with girth six
Dvorak, Zdenek
Kral, Daniel
Nejedly, Pavel
Skrekovski, Riste
[J]. EUROPEAN JOURNAL OF COMBINATORICS, 2008, 29 (04) : 838 - 849
[10] THE LIST CHROMATIC INDEX OF A BIPARTITE MULTIGRAPH
GALVIN, F
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 63 (01) : 153 - 158

← 1 2 →