【摘要】 图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.更多还原

【Abstract】 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.更多还原