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

Upper Bound on Chromatic Number of Square Graph of Sparse Graphs

图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.