Total coloring of graphs embedded in surfaces of nonnegative Euler characteristic

被引:6
作者
Wang HuiJuan [1 ]
Liu Bin [2 ]
Wu JianLiang [1 ]
Wang Bing [1 ,3 ]
机构
[1] Shandong Univ, Sch Math, Jinan 250100, Peoples R China
[2] Ocean Univ China, Dept Math, Qingdao 266100, Peoples R China
[3] Zaozhuang Univ, Dept Math, Zaozhuang 277160, Peoples R China
基金
中国国家自然科学基金;
关键词
total coloring; Euler characteristic; surface; TOTAL CHROMATIC NUMBER; PLANAR GRAPHS; 4-CYCLES;
D O I
10.1007/s11425-013-4576-2
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let G be a graph which can be embedded in a surface of nonnegative Euler characteristic. In this paper, it is proved that the total chromatic number of G is Delta(G) + 1 if Delta(G) >= 9, where Delta(G) is the maximum degree of G.
引用
收藏
页码:211 / 220
页数:10
相关论文
共 18 条
  • [1] [Anonymous], 1968, USPEKHIMAT NAUK
  • [2] Behzad M., 1965, Doctoral Thesis
  • [3] BORODIN OV, 1989, J REINE ANGEW MATH, V394, P180
  • [4] Planar graphs with maximum degree 8 and without intersecting chordal 4-cycles are 9-totally colorable
    Cai JianSheng
    Wang GuangHui
    Yan GuiYing
    [J]. SCIENCE CHINA-MATHEMATICS, 2012, 55 (12) : 2601 - 2612
  • [5] Hou J.F., 2008, SCI CHINA SER A, V51, P2127
  • [6] Total coloring of planar graphs without 6-cycles
    Hou, Jianfeng
    Liu, Bin
    Liu, Guizhen
    Wu, Jianliang
    [J]. DISCRETE APPLIED MATHEMATICS, 2011, 159 (2-3) : 157 - 163
  • [7] TOTAL COLORING OF A MULTI-GRAPH WITH MAXIMAL DEGREE-4
    KOSTOCHKA, AV
    [J]. DISCRETE MATHEMATICS, 1977, 17 (02) : 161 - 163
  • [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] Total colorings and list total colorings of planar graphs without intersecting 4-cycles
    Liu, Bin
    Hou, Jianfeng
    Wu, Jianliang
    Liu, Guizhen
    [J]. DISCRETE MATHEMATICS, 2009, 309 (20) : 6035 - 6043