Acyclic total colorings of planar graphs without l cycles

被引：0
作者：
Xiang Yong Sun
Jian Liang Wu
机构：
[1] Shandong Economic University,School of Statistics and Mathematics
[2] Shandong University,School of Mathematics and Systems Science
来源：
Acta Mathematica Sinica, English Series | 2011年 / 27卷
关键词：
Acyclic total coloring; cycle; planar graph; O5C15;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
A proper total coloring of a graph G such that there are at least 4 colors on those vertices and edges incident with a cycle of G, is called acyclic total coloring. The acyclic total chromatic number of G is the least number of colors in an acyclic total coloring of G. In this paper, it is proved that the acyclic total chromatic number of a planar graph G of maximum degree at least k and without l cycles is at most Δ(G) + 2 if (k, l) ∈ {(6, 3), (7, 4), (6, 5), (7, 6)}.
引用
收藏
页码：1315 / 1322
页数：7
相关论文
共 28 条
[1]  
Grunbaum B.(1973)Acyclic colorings of planar graphs Israsel J. Math. 14 390-408
[2]  
Borodin O. V.(1979)On acyclic colorings of planar graphs Discrete Math. 25 211-236
[3]  
Fertin G.(2008)Acyclic coloring of graphs of maximum degree five: Nine colors are enough Inform. Process. Lett. 105 65-72
[4]  
Raspaud A.(1991)Acyclic coloring of graphs Random Structures Algorithms 2 277-288
[5]  
Alon N.(1998)Further algorithmic aspects of the local lemma Proc. ACM Sympos. Theory Computing 30 524-529
[6]  
McDiarmid C. J. H.(2001)Acyclic edge colorings of graphs J. Graph Theory 37 157-167
[7]  
Reed B. A.(2002)Algorithmic aspects of acyclic edge colorings Algorithmica 32 611-614
[8]  
Molloy M.(2008)About acyclic edge colorings of planar graphs Inform. Process. Lett. 108 412-417
[9]  
Reed B.(2008)Acyclic edge colorings of planar graphs and series-parallel graphs Sci. China Ser. A 38 1335-1346
[10]  
Alon N.(1964)On an estimate of the chromatic class of a Metody Diskret Analiz 3 25-30
123