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

山东大学学报(理学版) ›› 2016, Vol. 51 ›› Issue (4): 72-78.doi: 10.6040/j.issn.1671-9352.0.2015.041

• • 上一篇    下一篇

不含6-圈和相邻5-圈的平面图的全染色

谭香   

  1. 山东财经大学数学与数量经济学院, 山东 济南 250014
  • 收稿日期:2015-01-19 出版日期:2016-04-20 发布日期:2016-04-08
  • 作者简介:谭香(1976— ),女,博士研究生,副教授,研究方向为图论与组合最优化. E-mail:xtandw@126.com
  • 基金资助:
    国家自然科学基金资助项目(11401386);山东省自然科学基金资助项目(ZR2013AM006);山东省高等学校科技计划项目(J14LI55)

Total colorings of planar graphs without 6-cycles and adjacent 5-cycles

TAN Xiang   

  1. School of Mathematics and Quantitative Economics, Shandong University of Finace and Ecnomics, Jinan 250014, Shandong, China
  • Received:2015-01-19 Online:2016-04-20 Published:2016-04-08

摘要: 设G是最大度Δ≥6的平面图。证明了若G不含6-圈和相邻的5-圈,则全染色数χ″(G)=Δ+1。

关键词: 平面图, 相邻5-圈, 全染色

Abstract: Let G be a planar graph with maximum degree Δ≥6. It is proved that if G contains no 6-cycles and adjacent 5-cycles, then the total chromatic χ″(G) is Δ+1.

Key words: planar graph, total coloring, adjacent 5-cycle

中图分类号: 

  • O157
[1] BONDYJ A, MURTY U S R. Graph theory with applications[M]. New York: North-Holland, 1976.
[2] BEHZAD M. Graphs and their chromatic numbers[D]. East Lansing: Michigan State University, 1965.
[3] VIZING V G. Some unresolvedproblems in graph theory[J]. Uspekhi Mat Nauk, 1968, 23: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]. J Graph Theory, 1999, 31:67-73.
[6] BORODIN O V, KOSTOCHKA A V, WOODALL D R. Total colorings of planar graphs with large maximum degree[J]. J Graph Theory, 1997, 26:53-59.
[7] WANG Weifan. Total chromatic number of planar graphs with maximum degreeten[J]. J Graph Theory, 2007, 54:91-102.
[8] KOWALIK L, SERENI J S,(~overS)KREKROVSKI R. Total-Coloring of plane graphs with maximum degree nine[J]. SIAM J Discrete Math, 2008, 22:1462-1479.
[9] HOU Jianfeng, LIU Bin, LIU Guizhen, et al. Total colorings of planar graphswithout 6-cycles[J]. Discrete Applied Mathematics, 2011, 159(8):157-163.
[10] CHANG G J, HOU Jianfeng, ROUSSEL N. Local condition for planar graphs ofmaximum degree 7 to be 8-totally-colorable[J]. Discrete Applied Mathematics, 2011, 159(8):760-768.
[11] SHEN Lan, WANG Yingqian. On the 7total colorability of planar graphswith maximum degree 6 and without 4-cycles[J]. Graphs and Combinatorics, 2009, 25:401-407.
[12] CAI Jiansheng, WANG Guanghui, YAN Guiying. Total colorings of planar graphswith maximum degree 8 and without intersecting chordal 4-cycles are 9-totally-colorable[J]. Sci China A, 2012, 55:2601-2612.
[13] WANG Huijuan, WU Jianliang. Total coloring of planar graphs withmaximum degree 8[J]. Theor Comput Sci, 2014, 522:54-61.
[14] 王应前,孙强,陶鑫,等. 最大度为7且不含带弦5-圈的平面图是8-全可染的[J].中国科学:A辑,2011,41(1):95-104. WANG Yingqian, SUN Qiang, TAO Xin, et al. Plane graphs with maximum degree 7 and without 5-cycles with chords are 8-totally colorable[J]. Sci China A, 2011, 41(1):95-104.
[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] 王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报(理学版), 2017, 52(8): 100-106.
[4] 陈祥恩,苗婷婷,王治文. 两条路的联图的点可区别I-全染色[J]. 山东大学学报(理学版), 2017, 52(4): 30-33.
[5] 王晔,孙磊. 不含3圈和4圈的1-平面图是5-可染的[J]. 山东大学学报(理学版), 2017, 52(4): 34-39.
[6] 陈宏宇,张丽. 4-圈不共点的平面图的线性2-荫度[J]. 山东大学学报(理学版), 2017, 52(12): 36-41.
[7] 何玉萍,王治文,陈祥恩. mC8的点可区别全染色[J]. 山东大学学报(理学版), 2017, 52(10): 24-30.
[8] 李世玲, 陈祥恩,王治文. 完全二部图K3,n(n≥18)的点可区别E-全染色[J]. 山东大学学报(理学版), 2016, 51(4): 68-71.
[9] 宋红杰,巩相男,潘文华,徐常青. Halin图的邻和可区别全染色[J]. 山东大学学报(理学版), 2016, 51(4): 65-67.
[10] 朱海洋,顾 毓,吕新忠. 平面图的平方染色数的一个新上界[J]. 山东大学学报(理学版), 2016, 51(2): 94-101.
[11] 孟宪勇, 郭建华, 苏本堂. 3-正则Halin图的完备染色[J]. 山东大学学报(理学版), 2015, 50(12): 127-129.
[12] 孟献青. 一类平面图的强边染色[J]. 山东大学学报(理学版), 2015, 50(08): 10-13.
[13] 何雪, 田双亮. 若干图的倍图的邻点可区别边(全)染色[J]. 山东大学学报(理学版), 2015, 50(04): 63-66.
[14] 李敬文, 贾西贝, 董威, 李小慧, 闫光辉. 图的邻点可区别全染色算法[J]. 山东大学学报(理学版), 2015, 50(02): 14-21.
[15] 姚京京, 徐常青. 最大度为3或4的图的邻和可区别全染色[J]. 山东大学学报(理学版), 2015, 50(02): 9-13.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!