您的位置:山东大学 -> 科技期刊社 -> 《山东大学学报(理学版)》

山东大学学报(理学版) ›› 2017, Vol. 52 ›› Issue (8): 100-106.doi: 10.6040/j.issn.1671-9352.0.2016.363

• • 上一篇    下一篇

最大度为7的平面图全染色

王晓丽1,王慧娟2*,刘彬1   

  1. 1.中国海洋大学数学科学学院, 山东 青岛 266100;2.青岛大学数学与统计学院, 山东 青岛 266071
  • 收稿日期:2016-07-23 出版日期:2017-08-20 发布日期:2017-08-03
  • 通讯作者: 王慧娟(1985— ), 女, 讲师, 博士, 研究方向为图论与组合最优化. E-mail:sduwhj@163.com E-mail:1519432029@qq.com
  • 作者简介:王晓丽(1991— ), 女, 硕士, 研究方向为图论与组合最优化. E-mail:1519432029@qq.com
  • 基金资助:
    国家自然科学基金资助项目(11501316);中国博士后科学基金(2015M570568,2016T90607);山东省自然科学基金资助项目(ZR2014AQ001);青岛博士后应用研究项目(2015170)

Total coloring of planar graphs with maximum degree seven

WANG Xiao-li1, WANG Hui-juan2*, LIU Bin1   

  1. 1. School of Mathematical Sciences, Ocean University of China, Qingdao 266100, Shandong, China;
    2. School of Mathematics and Statistics, Qingdao University, Qingdao 266071, Shandong, China
  • Received:2016-07-23 Online:2017-08-20 Published:2017-08-03

摘要: 假设图G是最大度为7的平面图利用权转移的方法证明了,如果图G中弦5-圈和弦6-圈不相邻,那么图G的全色数是Δ+1。

关键词: 平面图, 全染色, 圈, 权转移

Abstract: Let G be a planar graph with maximum degree Δ≥7. It is proved that if chordal 5-cycles of G are not adjacent to chordal 6-cycles, then its total chromatic number is Δ+1 by the discharging method.

Key words: total coloring, cycle, planar graph, discharging

中图分类号: 

  • O157.5
[1] BONDY J A, MURTY U S R. Graph theory with applications[M]. London: MacMillan, 1976.
[2] BEHZAD M. Graphs and their chromatic numbers[D]. Michigan: Michigan State University, 1965.
[3] VIZING V G. Some unsolved problems in graph theory[J]. Uspekhi Mat Nauk, 1968, 23(6):117-134.
[4] KOSTOCHKA A V. The total chromatic number of any multigraph with maximum degree five is at most seven[J]. Discrete Mathematics, 1996, 162:199-214.
[5] SANDERS D P, ZHAO Yue. On total 9-coloring planar graphs of maximum degree seven[J]. Journal of Graph Theory, 1999, 31(1):67-73.
[6] 王应前, 孙强, 陶鑫, 等. 最大度为7且不含带弦5-圈的平面图是8-全可染的[J]. 中国科学, 2011, 41(1):95-104. WANG Yingqian, SUN Qiang, TAO Xin, et al. Planar graphs with maximum degree 7 and without 5-cycles with chords are 8-totally-colorable[J]. Scientia Sinica, 2011, 41(1):95-104.
[7] WANG Bin, WU Jianliang, WANG Huijuan. Total coloring of planar graphs without chordal 6-cycles[J]. Discrete Applied Mathematics, 2014, 171:116-121.
[8] WANG Huijuan, LUO Zhaoyang, LIU Bin, et al. A note on the minimum total coloring of planar graphs[J]. Acta Mathematic Sinica, 2016, 32(8):967-974.
[9] BORODIN O V. On the total coloring of planar graphs[J]. Journal Für Die Reine Und Angewandte Mathematik, 1989, 394:180-185.
[10] WANG Ping, WU Jianliang. A note on total colorings of planar graphs without 4-cycles[J]. Discussiones Mathematicae Graph Theory, 2004, 24(1):125-135.
[11] CHANG G J, HOU Jianfeng, ROUSSEL N. Local condition for planar graphs of maximum degree 7 to be 8-totally colorable[J]. Discrete Applied Mathematics, 2011, 159(8):760-768.
[12] BORODIN O V, KOSTOCHKA A V, WOODALL D R. Total colorings of planar graphs with large maximum degree[J]. Journal of Graph Theory, 1997, 26(1):53-59.
[13] LIU Bin, HOU Jianfeng, WU Jianliang, et al. Total colorings and list total colorings of planar graphs without intersecting 4-cycles[J]. Discrete Mathematics, 2009, 309(20):6035-6043.
[14] SHEN Lan, WANG Yingqian. Total colorings of planar graphs with maximum degree at least 8[J]. Scince in China Series A: Mathematics, 2009, 52(8):1733-1742.
[15] WANG Weifan. Total chromatic number of planar graphs with maximum degree ten[J]. Graph Theory, 2007, 54(2):91-102.
[16] KOWALIK L, SERENI J S, SKREKOVSKI R. Total-coloring of plane graphs with maximum degree nine[J]. Siam Journal on Discrete Mathematics, 2008, 22(4):1462-1479.
[1] 寇艳芳,陈祥恩,王治文. K1,3,p K1,4,p的点可区别的IE-全染色及一般全染色[J]. 山东大学学报(理学版), 2018, 53(8): 53-60.
[2] 房启明,张莉. 无4-圈和5-圈的平面图的k-frugal列表染色[J]. 山东大学学报(理学版), 2018, 53(10): 35-41.
[3] 陈祥恩,苗婷婷,王治文. 两条路的联图的点可区别I-全染色[J]. 山东大学学报(理学版), 2017, 52(4): 30-33.
[4] 王晔,孙磊. 不含3圈和4圈的1-平面图是5-可染的[J]. 山东大学学报(理学版), 2017, 52(4): 34-39.
[5] 陈宏宇,张丽. 4-圈不共点的平面图的线性2-荫度[J]. 山东大学学报(理学版), 2017, 52(12): 36-41.
[6] 何玉萍,王治文,陈祥恩. mC8的点可区别全染色[J]. 山东大学学报(理学版), 2017, 52(10): 24-30.
[7] 李世玲, 陈祥恩,王治文. 完全二部图K3,n(n≥18)的点可区别E-全染色[J]. 山东大学学报(理学版), 2016, 51(4): 68-71.
[8] 谭香. 不含6-圈和相邻5-圈的平面图的全染色[J]. 山东大学学报(理学版), 2016, 51(4): 72-78.
[9] 白丹,左连翠. 立方圈的(d,1)-全标号[J]. 山东大学学报(理学版), 2016, 51(4): 59-64.
[10] 宋红杰,巩相男,潘文华,徐常青. Halin图的邻和可区别全染色[J]. 山东大学学报(理学版), 2016, 51(4): 65-67.
[11] 朱海洋,顾 毓,吕新忠. 平面图的平方染色数的一个新上界[J]. 山东大学学报(理学版), 2016, 51(2): 94-101.
[12] 孟宪勇, 郭建华, 苏本堂. 3-正则Halin图的完备染色[J]. 山东大学学报(理学版), 2015, 50(12): 127-129.
[13] 薛丽霞, 李志慧, 谢佳丽. 对3条超边的超圈存取结构最优信息率的一点注记[J]. 山东大学学报(理学版), 2015, 50(11): 60-66.
[14] 王珊珊, 齐恩凤. k-连通图中最长圈上可收缩边的数目[J]. 山东大学学报(理学版), 2015, 50(10): 27-31.
[15] 孟献青. 一类平面图的强边染色[J]. 山东大学学报(理学版), 2015, 50(08): 10-13.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!