JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2016, Vol. 51 ›› Issue (4): 72-78.doi: 10.6040/j.issn.1671-9352.0.2015.041

Previous Articles     Next Articles

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

PDF (PC)

821

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

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