Total coloring of embedded graphs of maximum degree at least ten

被引：0
作者：
HOU JianFeng 1
2 School of Mathematics
机构：
来源：
ScienceChina(Mathematics) | 2010年 / 53卷 / 08期
基金：
中国国家自然科学基金;
关键词：
surface; Euler characteristic; total coloring; total chromatic number;
D O I：
暂无
中图分类号：
O157.5 [图论];
学科分类号：
070104 ;
摘要：
A total k-coloring of a graph G is a coloring of V(G) ∪ E(G) using k colors such that no two adjacent or incident elements receive the same color.The total chromatic number χ〃(G) is the smallest integer k such that G has a total k-coloring.In this paper,it is proved that the total chromatic number of any graph G embedded in a surface Σ of Euler characteristic χ(Σ)≥0 is Δ(G) + 1 if Δ(G)≥10,where Δ(G) denotes the maximum degree of G.
引用
收藏
页码：2127 / 2133
页数：7
相关论文
共 5 条
  • [1] 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
  • [2] List edge and list total colorings of planar graphs without 4-cycles[J] . Jianfeng Hou,Guizhen Liu,Jiansheng Cai.Theoretical Computer Science . 2006 (1)
  • [3] Total colourings of planar graphs with large girth
    Borodin, OV
    Kostochka, AV
    Woodall, DR
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 1998, 19 (01) : 19 - 24
  • [4] The total chromatic number of any multigraph with maximum degree five is at most seven[J] . A.V. Kostochka.Discrete Mathematics . 1996 (1)
  • [5] On the total coloring of certain graphs[J] . M. Rosenfeld.Israel Journal of Mathematics . 1971 (3)
1