Coloring the square of maximal planar graphs with diameter two

被引：0

作者：

Wang, Yiqiao ^{[1
]}

Huo, Jingjing ^{[2
]}

Kong, Jiangxu ^{[3
]}

Tan, Qiuyue ^{[4
]}

机构：

[1] Beijing Univ Technol, Fac Sci, Beijing 100124, Peoples R China

[2] Hebei Univ Engn, Dept Math, Handan 056038, Peoples R China

[3] Hangzhou Normal Univ, Sch Math, Hangzhou 311121, Peoples R China

[4] Wuyi Univ, Dept Math & Comp, Wuyishan 354300, Peoples R China

来源：

APPLIED MATHEMATICS AND COMPUTATION | 2023年 / 459卷

关键词：

Wegner's conjecture; Chromatic number; Maximal planar graph; Diameter; 4-CYCLES; GIRTH;

D O I：

10.1016/j.amc.2023.128263

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Let G be a maximal planar graph with diameter two and maximum degree Delta. Let chi (G2) denote the chromatic number of the square of... In this paper, we prove that chi(G2) = Delta + 1 if 2 <= Delta <= 3; chi(G(2)) <= 6 if Delta = 4; chi(G(2)) = 9 if Delta + 5; chi(G2) <=+ 5 if 6 <= Delta <= 7; and chi(G2) <= 3 Delta/2 + 1 if >= 8. All bounds are tight. This confirms the Wegner's conjecture for maximal planar graphs with diameter two.

引用

页数：10

共 12 条

[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] Planar graphs of girth at least five are square (Δ+2)-choosable
Bonamy, Marthe
Cranston, Daniel W.
Postle, Luke
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2019, 134 : 218 - 238
[3] The sizes of maximal planar, outerplanar, and bipartite planar subgraphs
Cimikowski, R
Coppersmith, D
[J]. DISCRETE MATHEMATICS, 1996, 149 (1-3) : 303 - 309
[4] 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
[5] LARGEST PLANAR GRAPHS OF DIAMETER 2 AND FIXED MAXIMUM DEGREE
HELL, P
SEYFFARTH, K
[J]. DISCRETE MATHEMATICS, 1993, 111 (1-3) : 313 - 322
[6] 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
[7] MAXIMAL PLANAR GRAPHS OF DIAMETER 2
SEYFFARTH, K
[J]. JOURNAL OF GRAPH THEORY, 1989, 13 (05) : 619 - 648
[8] The square of a planar cubic graph is 7-colorable
Thomassen, Carsten
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2018, 128 : 192 - 218
[9] Coloring the square of a planar graph
van den Heuvel, J
McGuinness, S
[J]. JOURNAL OF GRAPH THEORY, 2003, 42 (02) : 110 - 124
[10] Labelling planar graphs without 4-cycles with a condition on distance two
Wang, Weifan
Cai, Leizhen
[J]. DISCRETE APPLIED MATHEMATICS, 2008, 156 (12) : 2241 - 2249

← 1 2 →