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

发布时间：2021-02-14 01:56

　　图G的平方G²定义为顶点集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. 

【文章来源】：吉林大学学报(理学版). 2020,58(03)北大核心

【文章页数】：15 页

【文章目录】：
1 引言与主要结果
2 定理4的证明
    2.1 相关命题
    2.2 权转移规则
        2.2.1 3--点
        2.2.2 坏顶点
        2.2.3 B型弱坏顶点 令v是图G的B型弱坏顶点.
        2.2.4 A型弱坏顶点 令v是图G的A型弱坏顶点.
        2.2.5 弱好顶点
        2.2.6 好顶点
3 定理5的证明
    3.1 相关命题
    3.2 权转移规则
        3.2.1 4--点
        3.2.2 坏顶点
        3.2.3 B型弱坏顶点
        3.2.4 A型弱坏顶点 令v是图G的A型弱坏顶点.
        3.2.5 弱好顶点
        3.2.6 好顶点



本文编号：3032933