稀疏图平方图的染色数上界

吉林大学学报(理学版) ›› 2020, Vol. 58 ›› Issue (3): 575-589.

稀疏图平方图的染色数上界

张艳

天津大学应用数学中心, 天津 300072

收稿日期:2019-08-29 出版日期:2020-05-26 发布日期:2020-05-20
通讯作者: 张艳 E-mail:mathzhangyan@tju.edu.cn

Upper Bound on Chromatic Number of Square Graph of Sparse Graphs

ZHANG Yan

Center for Applied Mathematics, Tianjin University, Tianjin 300072, China

Received:2019-08-29 Online:2020-05-26 Published:2020-05-20
Contact: ZHANG Yan E-mail:mathzhangyan@tju.edu.cn

摘要/Abstract

摘要： 图G的平方G2定义为顶点集V(G)=V(G²), 并且uv∈E(G²)当且仅当u和v之间的距离至多为2. G²的色数χ(G²)是指使得G²存在正常k顶点染色的最小整数k. 用权转移的方法证明: 如果mad(G)<4且Δ(G)≥7, 则χ(G²)≤3Δ(G)+1;
如果mad(G)≤4且Δ(G)≥8, 则χ(G²)≤3Δ(G)+5.

关键词: k顶点染色, 平方图, 最大平均度, 色数

Abstract: The square G² of a graph G is a graph such that V(G)=V(G²) and uv∈E(G²) if and only if the distance between u and v is at most two. The chromatic number χ(G²) of G² is the minimum k for which G² has a proper k vertexcoloring. Using the discharging method, the author proves that if mad(G)<4 and Δ(G)≥7, then χ(G²)≤3Δ(G)+1, if mad(G)≤4 and Δ(G)≥8, then χ(G²)≤3Δ(G)+5.

Key words: k vertex coloring, square graph, , maximum average degree, chromatic number

中图分类号:

O157.5

张艳. 稀疏图平方图的染色数上界[J]. 吉林大学学报(理学版), 2020, 58(3): 575-589.

ZHANG Yan. Upper Bound on Chromatic Number of Square Graph of Sparse Graphs[J]. Journal of Jilin University Science Edition, 2020, 58(3): 575-589.

[1]	贾秀卿, 李沐春. 单圈图的D(2)-点可区别边染色[J]. 吉林大学学报(理学版), 2021, 59(4): 807-815.
[2]	赵亚迪, 陈祥恩. 图mC₁₅的点可区别Ⅰ-全染色和Ⅵ-全染色[J]. 吉林大学学报(理学版), 2021, 59(3): 497-512.
[3]	杨晗, 陈祥恩. 图mC₈的点可区别Ⅰ-全染色和Ⅵ-全染色[J]. 吉林大学学报(理学版), 2021, 59(2): 241-249.
[4]	杨佳睿, 陈祥恩. K_3,5,p的点可区别的一般全染色[J]. 吉林大学学报(理学版), 2020, 58(4): 832-840.
[5]	杨青, 田双亮, 索郎王青. 图的冠积和边冠积的b-染色[J]. 吉林大学学报(理学版), 2020, 58(3): 590-594.
[6]	杨伟光, 陈祥恩. 完全二部图K_9,n(9≤n≤92)的点可区别E-全染色[J]. 吉林大学学报(理学版), 2020, 58(2): 301-308.
[7]	李婷, 陈祥恩, 王治文. 2K₂∨K₁冠图的一般点可区别全染色[J]. 吉林大学学报(理学版), 2019, 57(3): 544-552.
[8]	张辉, 陈祥恩, 王治文. 两圈之联、路与圈的联及两路之联的邻点被扩展和可区别全染色#br#[J]. 吉林大学学报(理学版), 2018, 56(6): 1402-1408.
[9]	师志凤, 陈祥恩, 王治文. 完全二部图K_6,n(6≤n≤38)的点可区别E全染色[J]. 吉林大学学报(理学版), 2018, 56(4): 845-852.
[10]	寇艳芳, 陈祥恩, 王治文. K_1,1,p,K_1,2,p的点可区别的IE-全染色及一般全染色[J]. 吉林大学学报(理学版), 2018, 56(2): 299-305.
[11]	何玉萍, 王治文, 陈祥恩. mC₇的点可区别全染色[J]. 吉林大学学报(理学版), 2017, 55(03): 531-536.
[12]	张婷, 朱恩强, 刘晓娜, 赵双柱. 若干联图的邻点可区别I-全染色[J]. 吉林大学学报(理学版), 2017, 55(02): 267-272.
[13]	陈祥恩, 苏丽, 王治文. 完全二部图K_2,n和K_3,n的一般点可区别全染色[J]. 吉林大学学报(理学版), 2016, 54(06): 1289-1293.
[14]	王蓓蓓, 祁丽娟, 刘信生, 陈祥恩. 完全二部图K_6,8的点强可区别全染色[J]. 吉林大学学报(理学版), 2016, 54(05): 1027-1031.
[15]	陈祥恩, 何玉萍. D(d)-VDTC猜想的反例[J]. 吉林大学学报(理学版), 2016, 54(01): 66-69.