JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2017, Vol. 52 ›› Issue (8): 100-106.doi: 10.6040/j.issn.1671-9352.0.2016.363

Previous Articles     Next Articles

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

PDF (PC)

843

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

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   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd