山东大学学报（理学版） ›› 2017, Vol. 52 ›› Issue (8): 100-106.doi: 10.6040/j.issn.1671-9352.0.2016.363
王晓丽1,王慧娟2*,刘彬1
WANG Xiao-li1, WANG Hui-juan2*, LIU Bin1
摘要： 假设图G是最大度为7的平面图。 利用权转移的方法证明了,如果图G中弦5-圈和弦6-圈不相邻,那么图G的全色数是Δ+1。
中图分类号:
| [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. |
|
||
