List 2-distance -coloring of planar graphs without 4,5-cycles

被引：0

作者：

Zhu, Haiyang ^{[1
]}

Gu, Yu ^{[1
]}

Sheng, Jingjun ^{[1
]}

Lu, Xinzhong ^{[2
]}

机构：

[1] Air Force Logist Coll, Dept Flight Support Command, Xuzhou 221000, Jiangsu, Peoples R China

[2] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Peoples R China

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2018年 / 36卷 / 04期

关键词：

2-Distance coloring; Planar graph; Wegner's conjecture; List L(2,1)-labeling; SQUARE; CHOOSABILITY; 4-CYCLES; GIRTH;

D O I：

10.1007/s10878-018-0312-8

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Let and be the 2-distance chromatic number and list 2-distance chromatic number of a graph G, respectively. Wegner conjectured that for each planar graph G with maximum degree at least 4, if , and if . Let G be a planar graph without 4,5-cycles. We show that if , then . There exist planar graphs G with girth such that for arbitrarily large . In addition, we also discuss the list L(2, 1)-labeling number of G, and prove that for Delta >= 27.

引用

页码：1411 / 1424

页数：14

共 21 条

[1] A unified approach to distance-two colouring of graphs on surfaces
Amini, Omid
Esperet, Louis
Van den Heuvel, Jan
[J]. COMBINATORICA, 2013, 33 (03) : 253 - 296
[2] 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
[3] Bondy J., 2008, GRADUATE TEXTS MATH
[4] List 2-distance (Δ+2)-coloring of planar graphs with girth 6 and Δ aparts per thousandyen 24
Borodin, O. V.
Ivanova, A. O.
[J]. SIBERIAN MATHEMATICAL JOURNAL, 2009, 50 (06) : 958 - 964
[5] Borodin OV, 2006, SIB ELECTRON MATH RE, V3, P355
[6] Borodin O.V., 2004, Siberian Electronic Math. Reports, V1, P129
[7] BORODIN OV, 1989, J REINE ANGEW MATH, V394, P180
[8] Borodin OV, 2002, TECHNICAL REPORT
[9] List-Coloring the Squares of Planar Graphs without 4-Cycles and 5-Cycles
Cranston, Daniel W.
Jaeger, Bobby
[J]. JOURNAL OF GRAPH THEORY, 2017, 85 (04) : 721 - 737
[10] 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

← 1 2 3 →