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

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.

CLC Number:

• 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] . 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] WANG Xiao-li, WANG Hui-juan, LIU Bin. Total coloring of planar graphs with maximum degree seven [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 100-106. [4] 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. [5] 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. [6] 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. [7] 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. [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] 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. [10] 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. [11] 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. [12] HE Xue, TIAN Shuang-liang. Adjacent vertex-distinguishing edge/total colorings of double graph of some graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(04): 63-66. [13] LI Jing-wen, JIA Xi-bei, DONG Wei, LI Xiao-hui, YAN Guang-hui. The algorithm for adjacent-vertex-distinguishing total coloring of graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 14-21. [14] YAO Jing-jing, XU Chang-qing. Neighbor sum distinguishing total coloring of graphs with maximum degree 3 or 4 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 9-13. [15] LIU Xin-sheng, DENG Wei-dong, WANG Zhi-qiang. Several conclusions of adjacent vertex distinguishing E-total coloring of the cartesian product graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 5-8.
Viewed
Full text

Abstract

Cited

Shared
Discussed