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

Upper Bound on Chromatic Number of Square Graph of Sparse Graphs

作　　者：张艳 ZHANG Yan(Center for Applied Mathematics,Tianjin University,Tianjin 300072,China)

机构地区：[1]天津大学应用数学中心,天津300072

出　　处：《吉林大学学报（理学版）》2020年第3期575-589,共15页Journal of Jilin University:Science Edition

基　　金：国家自然科学基金(批准号:11601380).

摘　　要：图G的平方^G^2定义为顶点集V(G)=V(^G^2),并且uv∈E(^G^2)当且仅当u和v之间的距离至多为2.^G^2的色数χ(^G^2)是指使得^G^2存在正常k-顶点染色的最小整数k.用权转移的方法证明:如果mad(G)<4且Δ(G)≥7,则χ(^G^2)≤3Δ(G)+1;如果mad(G)≤4且Δ(G)≥8,则χ(^G^2)≤3Δ(G)+5.The square ^G^2 of a graph G is a graph such that V(G)=V(^G^2) and uv∈E(^G^2) if and only if the distance between u and v is at most two. The chromatic number χ(^G^2) of ^G^2 is the minimum k for which ^G^2 has a proper k-vertex-coloring. Using the discharging method, the author proves that if mad(G)<4 and Δ(G)≥7, then χ(^G^2)≤3Δ(G)+1, if mad(G)≤4 and Δ(G)≥8, then χ(^G^2)≤3Δ(G)+5.

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

分 类 号：O157.5[理学—数学]