Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable

被引：38

作者：

Du, Dingzhu ^{[1
]}

Shen, Lan ^{[1
]}

Wang, Yingqian ^{[1
]}

机构：

[1] Zhejiang Normal Univ, Coll Math Phys & Informat Engn, Jinhua 321004, Zhejiang, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2009年 / 157卷 / 13期

关键词：

Planar graph; Total coloring; Maximum degree; Adjacent triangles; TOTAL COLORINGS; 4-CYCLES;

D O I：

10.1016/j.dam.2009.02.011

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The Total Coloring Conjecture, in short, TCC, says that every simple graph is (Delta + 2)-totally-colorable where Delta is the maximum degree of the graph. Even for planar graphs this conjecture has not been completely settled yet. However, every planar graph with Delta >= 9 has been proved to be (Delta + 1)-totally-colorable. In this paper, we prove that planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：2778 / 2784

页数：7

共 13 条

[1] [Anonymous], 1968, USPEKHIMAT NAUK
[2] Behzad M., 1965, Doctoral thesis
[3] Bondy J. A., 1976, Graduate Texts in Mathematics, V290
[4] Borodin OV, 1997, J GRAPH THEOR, V26, P53, DOI 10.1002/(SICI)1097-0118(199709)26:1<53::AID-JGT6>3.0.CO
[5] 2-G
[6] Total colourings of planar graphs with large girth
Borodin, OV
Kostochka, AV
Woodall, DR
[J]. EUROPEAN JOURNAL OF COMBINATORICS, 1998, 19 (01) : 19 - 24
[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] List edge and list total colorings of planar graphs without 4-cycles
Hou, Jianfeng
Liu, Guizhen
Cai, Jiansheng
[J]. THEORETICAL COMPUTER SCIENCE, 2006, 369 (1-3) : 250 - 255
[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] SHEN L, GRAPHS COMB IN PRESS

← 1 2 →