### 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

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.

CLC Number:

• 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] . Vertex-distinguishing IE-total coloring and general-total coloring of K1,3,p and K1,4,p [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(8): 53-60. [2] FANG Qi-ming, ZHANG Li. k-frugal list coloring of planar graphs without 4 and 5-cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 35-41. [3] CHEN Xiang-en, MIAO Ting-ting, WANG Zhi-wen. Vertex-distinguishing I-total colorings of the join of two paths [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(4): 30-33. [4] WANG Ye, SUN Lei. Every 1-planar graph without cycles of length 3 or 4 is 5-colorable [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(4): 34-39. [5] CHEN Hong-yu, ZHANG Li. Linear 2-arboricity of planar graphs with 4-cycles have no common vertex [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(12): 36-41. [6] HE Yu-ping, WANG Zhi-wen, CHEN Xiang-en. Vertex-distinguishing total coloring of mC8 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(10): 24-30. [7] YU Xiao-lan. Global dimensions of cocycle deformations [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(8): 39-43. [8] LI Shi-ling, CHEN Xiang-en, WANG Zhi-wen. Vertex-Distinguishing E-Total coloring of complete bipartite graph K3,n with n≥18 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 68-71. [9] TAN Xiang. Total colorings of planar graphs without 6-cycles and adjacent 5-cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 72-78. [10] BAI Dan, ZUO Lian-cui. The(d,1)-total labelling of the cube of cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 59-64. [11] SONG Hong-jie, GONG Xiang-nan, PAN Wen-hua, XU Chang-qing. Neighbor sum distinguishing total coloring of Halin graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 65-67. [12] WANG Jia-jiang, CHEN Ling, MEN Yu-tao, JI Chen. The feasibility study on shorten treatment cycle of dental implantation and split-root technique joint repair [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(3): 40-43. [13] ZHU Hai-yang, GU Yu, LÜ Xin-zhong. New upper bound on the chromatic number of the square of a planar graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(2): 94-101. [14] WU Zi-juan, CHEN Yuan-yuan, ZHANG Liang-yun. Quasidimodule algebras over Hopf quasigroups and Yetter-Drinfeld quasimodule algebras [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(10): 28-33. [15] MENG Xian-yong, GUO Jian-hua, SU Ben-tang. The complete coloring of 3-regular Halin graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(12): 127-129.
Viewed
Full text

Abstract

Cited

Shared
Discussed