2-distance choice number of planar graphs with maximal degree no more than 4

被引：0

作者：

Zhou, Wenjuan ^{[1
]}

Sun, Lei ^{[1
]}

机构：

[1] Shandong Normal Univ, Sch Math & Stat, Jinan 250014, Peoples R China

来源：

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS | 2021年 / 13卷 / 05期

基金：

中国国家自然科学基金;

关键词：

Planar graph; 2-distance k-choosable; girth; maximum degree;

D O I：

10.1142/S1793830921500518

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Regarding the 2-distance coloring of planar graphs, in 1977, Wegner conjectured that for a graph G: (1) chi(2)(G) <= 7 if Delta(G) = 3. (2) chi(2)(G) <= Delta(G) + 5 if 4 <= Delta(G) <= 7. (3) chi(2)(G) <= L left perpendicular3/2 Delta(G)right perpendicular + 1 if Delta(G) >= 8. In this paper, we proved that for every planar graph with maximum degree Delta(G) <= 4: (1) chi(l)(2)(G) <= 10 if g(G) >= 6. (2) chi(l)(2)(G) <= 7 if g(G) >= 10.

引用

页数：7

共 10 条

[1] 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
[2] Bondy J.A., 2007, Graph Theory
[3] Borodin O.V., 2009, DISCRETE MATH, V309, P23
[4] 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
[5] Dvorak Z., 2005, DISCRETE APPL MATH, V43, P976
[6] Havet F., 2007, Electron. Notes Discrete Math., V29, P515
[7] A bound on the chromatic number of the square of a planar graph
Molloy, M
Salavatipour, MR
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 94 (02) : 189 - 213
[8] Wegner G., 1977, Graphs with given diameter and a coloring problem
[9] Yan X.Y, 2014, J ZHEJIANG NORMAL U, V37
[10] Minimum 2-distance coloring of planar graphs and channel assignment
Zhu, Junlei
Bu, Yuehua
[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 36 (01) : 55 - 64

← 1 →