Minimum total coloring of planar graphs with maximum degree 8

被引：0

作者：

Wang, Liting ^{[1
]}

Wang, Huijuan ^{[1
]}

Wu, Weili ^{[2
]}

机构：

[1] Qingdao Univ, Sch Math & Stat, Qingdao 266071, Peoples R China

[2] Univ Texas Dallas, Dept Comp Sci, Richardson, TX 75080 USA

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2023年 / 45卷 / 02期

关键词：

Minimum total coloring; Planar graph; Maximum degree; TOTAL CHROMATIC NUMBER;

D O I：

10.1007/s10878-023-01011-y

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We define G to be a planar graph with maximum degree delta. Suppose delta >= 8 and G has no adjacent p,q-cycles for some p, q is an element of {3, 4, 5, 6, 7, 8}, then G can be totally colored by (delta + 1) colors.

引用

页数：11

共 19 条

[1] Behzad M., 1965, Graphs and their chromatic numbers
[2] Bondy J. A., 1976, Graph theory with applications
[3] Borodin OV, 1997, J GRAPH THEOR, V26, P53, DOI 10.1002/(SICI)1097-0118(199709)26:1<53::AID-JGT6>3.0.CO
[4] 2-G
[5] Total colorings of planar graphs with maximum degree 8 and without 5-cycles with two chords
Chang, Jian
Wang, Hui-Juan
Wu, Jian-Liang
A, Yong-Ga
[J]. THEORETICAL COMPUTER SCIENCE, 2013, 476 : 16 - 23
[6] Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable
Du, Dingzhu
Shen, Lan
Wang, Yingqian
[J]. DISCRETE APPLIED MATHEMATICS, 2009, 157 (13) : 2778 - 2784
[7] Total colorings of planar graphs without small cycles
Hou, Jianfeng
Zhu, Yan
Liu, Guizhen
Wu, Jianliang
Lan, Mei
[J]. GRAPHS AND COMBINATORICS, 2008, 24 (02) : 91 - 100
[8] The total chromatic number of any multigraph with maximum degree five is at most seven
Kostochka, AV
[J]. DISCRETE MATHEMATICS, 1996, 162 (1-3) : 199 - 214
[9] TOTAL-COLORING OF PLANE GRAPHS WITH MAXIMUM DEGREE NINE
Kowalik, Lukasz
Sereni, Jean-Sebastien
Skrekovski, Riste
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 22 (04) : 1462 - 1479
[10] DETERMINING THE TOTAL COLORING NUMBER IS NP-HARD
SANCHEZARROYO, A
[J]. DISCRETE MATHEMATICS, 1989, 78 (03) : 315 - 319

← 1 2 →