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

Abstract: The square G² of a graph G is a graph such that V(G)=V(G²) and uv∈E(G²) if and only if the distance between u and v is at most two. The chromatic number χ(G²) of G² is the minimum k for which G² has a proper k vertexcoloring. Using the discharging method, the author proves that if mad(G)<4 and Δ(G)≥7, then χ(G²)≤3Δ(G)+1,  if mad(G)≤4 and Δ(G)≥8, then χ(G²)≤3Δ(G)+5.

Key words: k vertex coloring, square graph,  , maximum average degree, chromatic number