论文部分内容阅读
图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.