您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2022, Vol. 57 ›› Issue (6): 61-63.doi: 10.6040/j.issn.1671-9352.0.2020.556

• • 上一篇    

3-退化图的全染色

杨腾飞,徐常青*   

  1. 河北工业大学理学院, 天津 300401
  • 发布日期:2022-06-10
  • 作者简介:杨腾飞(1995— ), 男, 硕士研究生, 研究方向为图论. E-mail:tfyang95@163.com*通信作者简介:徐常青(1970— ), 女, 博士, 教授, 硕士生导师, 研究方向为图论. E-mail:chqxu@hebut.edu.cn
  • 基金资助:
    国家自然科学基金资助项目(12071260,12001154);国家自然科学基金中韩项目(1211101361);河北省自然科学基金青年科学基金资助项目(A2021202025)

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)

163

摘要： 图G的 k-全染色指用k种颜色对图G的顶点和边进行染色,使得相邻或相关联的元素染不同的颜色。图G的全色数是指使得G有一个k-全染色的最小正整数k,记作χ″(G)。Behzad和Vizing独立提出了全染色猜想:对于任意图G,有χ″(G)≤Δ(G)+2。证明了对Δ(G)≥5的3-退化图全染色猜想成立。

关键词: 全染色, 全色数, 3-退化图

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

中图分类号: 

  • 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] 赵亚迪,陈祥恩. m个长为14的圈的不交并的点可区别Ⅰ-全染色[J]. 《山东大学学报(理学版)》, 2022, 57(6): 54-60.
[2] 马静静,陈祥恩. K4,4,p的点可区别一般全染色[J]. 《山东大学学报(理学版)》, 2022, 57(4): 48-54.
[3] 张生桂,陈祥恩. 近完全图的点可区别Ⅰ-全染色及Ⅵ-全染色[J]. 《山东大学学报(理学版)》, 2021, 56(5): 23-25.
[4] 杨晗,陈祥恩. mC7的点可区别Ⅰ-全染色和Ⅵ-全染色[J]. 《山东大学学报(理学版)》, 2021, 56(11): 76-82.
[5] 谭香. 一类最大度为6的平面图的全染色[J]. 《山东大学学报(理学版)》, 2021, 56(11): 71-75.
[6] 杨佳睿,陈祥恩. K3,3,p的点可区别的一般全染色[J]. 《山东大学学报(理学版)》, 2021, 56(1): 18-23.
[7] 寇艳芳,陈祥恩,王治文. K1,3,p和 K1,4,p的点可区别的IE-全染色及一般全染色[J]. 山东大学学报（理学版）, 2018, 53(8): 53-60.
[8] 包丽娅,陈祥恩,王治文. 完全二部图K10,n(10≤n≤90)的点可区别E-全染色[J]. 《山东大学学报(理学版)》, 2018, 53(12): 23-30.
[9] 王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报（理学版）, 2017, 52(8): 100-106.
[10] 陈祥恩,苗婷婷,王治文. 两条路的联图的点可区别I-全染色[J]. 山东大学学报（理学版）, 2017, 52(4): 30-33.
[11] 何玉萍,王治文,陈祥恩. mC8的点可区别全染色[J]. 山东大学学报（理学版）, 2017, 52(10): 24-30.
[12] 宋红杰,巩相男,潘文华,徐常青. Halin图的邻和可区别全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 65-67.
[13] 谭香. 不含6-圈和相邻5-圈的平面图的全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 72-78.
[14] 李世玲, 陈祥恩,王治文. 完全二部图K3,n(n≥18)的点可区别E-全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 68-71.
[15] 何雪, 田双亮. 若干图的倍图的邻点可区别边(全)染色[J]. 山东大学学报（理学版）, 2015, 50(04): 63-66.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发