A note on the minimum total coloring of planar graphs

被引:2
|
作者
Wang, Hui Juan [1 ]
Luo, Zhao Yang [2 ]
Liu, Bin [3 ]
Gu, Yan [1 ]
Gao, Hong Wei [1 ]
机构
[1] Qingdao Univ, Coll Math, Qingdao 266071, Peoples R China
[2] Changji Univ, Dept Math, Changji 831100, Peoples R China
[3] Ocean Univ China, Dept Math, Qingdao 266100, Peoples R China
基金
中国国家自然科学基金; 中国博士后科学基金;
关键词
Planar graph; total coloring; cycle; 5-CYCLES;
D O I
10.1007/s10114-016-5427-1
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Graph coloring is an important tool in the study of optimization, computer science, network design, e.g., file transferring in a computer network, pattern matching, computation of Hessians matrix and so on. In this paper, we consider one important coloring, vertex coloring of a total graph, which is also called total coloring. We consider a planar graph G with maximum degree Delta(G) a parts per thousand yen 8, and proved that if G contains no adjacent i, j-cycles with two chords for some i, j a {5, 6, 7}, then G is total-(Delta + 1)-colorable.
引用
收藏
页码:967 / 974
页数:8
相关论文
共 50 条
  • [31] Total coloring of planar graphs without adjacent chordal 6-cycles
    Wang, Huijuan
    Liu, Bin
    Wang, Xiaoli
    Tong, Guangmo
    Wu, Weili
    Gao, Hongwei
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (01) : 257 - 265
  • [32] Total Coloring of Planar Graphs Without Some Chordal 6-cycles
    Xu, Renyu
    Wu, Jianliang
    Wang, Huijuan
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2015, 38 (02) : 561 - 569
  • [33] Total coloring of recursive maximal planar graphs
    Zhou, Yangyang
    Zhao, Dongyang
    Ma, Mingyuan
    Xu, Jin
    THEORETICAL COMPUTER SCIENCE, 2022, 909 : 12 - 18
  • [34] A note on acyclic total coloring of plane graphs
    Dong, Wei
    ARS COMBINATORIA, 2016, 129 : 123 - 137
  • [35] A Note on 3-Distance Coloring of Planar Graphs
    Hasanvand, Morteza
    Ozeki, Kenta
    BULLETIN OF THE IRANIAN MATHEMATICAL SOCIETY, 2024, 50 (02)
  • [36] A Note on 3-Distance Coloring of Planar Graphs
    Morteza Hasanvand
    Kenta Ozeki
    Bulletin of the Iranian Mathematical Society, 2024, 50
  • [37] Total coloring of planar graphs with 7-cycles containing at most two chords
    Xu, Renyu
    Wu, Jian-Liang
    THEORETICAL COMPUTER SCIENCE, 2014, 520 : 124 - 129
  • [38] Total coloring of planar graphs without chordal 7-cycles
    Hua Cai
    Acta Mathematica Sinica, English Series, 2015, 31 : 1951 - 1962
  • [39] Total Coloring of Planar Graphs without Adacent 4-cycles
    Tan, Xiang
    Chen, Hong-Yu
    Wu, Jian-Liang
    OPERATIONS RESEARCH AND ITS APPLICATIONS, PROCEEDINGS, 2009, 10 : 167 - 173
  • [40] Total Coloring of Planar Graphs without Chordal 7-cycles
    Hua CAI
    Acta Mathematica Sinica,English Series, 2015, (12) : 1951 - 1962