JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2022, Vol. 57 ›› Issue (6): 61-63.doi: 10.6040/j.issn.1671-9352.0.2020.556

Previous Articles    

Total colorings of 3-degenerate graphs

YANG Teng-fei, XU Chang-qing*   

  1. School of Science, Hebei University of Technology, Tianjin 300401, China
  • Published:2022-06-10

PDF (PC)

153

Abstract: A k-total coloring of a graph G is a coloring of the vertices and edges with k colors, such that no two adjacent or incident elements receive the same color. The total chromatic number of a graph G is the smallest integer k such that G has a k-total coloring, denoted by χ″(G). Behzad and Vizing independently proposed the Total Coloring Conjecture that χ″(G)≤Δ(G)+2 for any graph G. In this paper, it is proved that the 3-degenerate graph with Δ(G)≥5 satisfies the total coloring Conjecture.

Key words: total coloring, total chromatic number, 3-degenerate graph

CLC Number: 

  • O157.5
[1] BONDY J, MURTY U. Graph theory with applications[M]. New York: Springer, 2008.
[2] BEHZAD M. Graphs and their chromatic numbers[D]. Michigan: Michigan State University, 1965.
[3] VIZING V. Some unsolved problems in graph theory[J]. Russian Mathematical Surveys, 1968, 23(6):117-134.
[4] ROSENFELD M. On the total coloring of certain graphs[J]. Israel Journal of Mathematics, 1971, 9(3):396-402.
[5] BORODIN O. On the total coloring of planar graphs[J]. Crelles Journal, 1989, 394:180-185.
[6] YAP H P. Total colourings of graphs[M] //Lecture Notes in Mathematics 1623. Berlin: Springer, 1996.
[7] SANDERS D, ZHAO Yue. On total 9-coloring planar graphs of maximum degree seven[J]. Journal of Graph Theory, 1999, 31(1):67-73.
[8] KOWALIK L, SERENI J, SKREKOVSKI R. Total coloring of plana graphs with maximum degree nine[J]. SIAM Journal on Discrete Mathematics, 2008, 22(4):1462-1479.
[9] WANG Weifan. Total chromatic number of planar graphs with maximum degree ten[J]. Journal of Graph Theory, 2007, 54(2):91-102.
[10] ISOBE S, ZHOU Xiao, NISHIZEKI T. Total colorings of degenerate graphs[J]. Combinatorica, 2007, 27(2):167-182.
[11] YANG Donglei, SUN Lin, YU Xiaowei, et al. Neighbor sum distinguishing total chromatic number of planar graphs with maximum degree 10[J]. Applied Mathematics and Computation, 2017, 314:456-468.
[1] ZHAO Ya-di, CHEN Xiang-en. Vertex-distinguishing Ⅰ-total colorings of mC14 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(6): 54-60.
[2] MA Jing-jing, CHEN Xiang-en. Vertex-distinguishing general-total coloring of K4,4,p [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(4): 48-54.
[3] ZHANG Sheng-gui, CHEN Xiang-en. Vertex-distinguishing Ⅰ-total coloring and Ⅵ-total coloring of almost complete graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(5): 23-25.
[4] YANG Han, CHEN Xiang-en. Vertex-distinguishing Ⅰ-total colorings and vertex-distinguishing Ⅵ-total colorings of mC7 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(11): 76-82.
[5] TAN Xiang. Total colorings of one type of planar graphs with maximum degree 6 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(11): 71-75.
[6] YANG Jia-rui, CHEN Xiang-en. Vertex-distinguishing general total coloring of K3,3,p [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(1): 18-23.
[7] . 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.
[8] . Vertex-distinguishing E-total coloring of complete bipartite graph K10,n with 10≤n≤90 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(12): 23-30.
[9] 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.
[10] 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.
[11] 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.
[12] 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.
[13] 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.
[14] 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.
[15] 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.
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