Lian Ying MIAO, Yi Zheng FAN
Let G be a connected graph with maximum degree Δ ≥ 3. We investigate the upper bound for the chromatic number χγ(G) of the power graph Gγ. It was proved that χγ(G)≤ Δ((Δ-1)γ-1)/(Δ-2)+1=:M+1, where the equality holds if and only if χγ(G) is a Moore graph. If χγ(G) is not a Moore graph, and G satisfies one of the following conditions:(1) G is non-regular, (2) the girth g(G) ≤ 2γ-1, (3) g(G) ≥ 2γ+2, and the connectivity κ(G) ≥ 3 if γ ≥ 3, κ(G)≥ 4 but κ(G) > 6 if γ=2, (4) Δ is sufficiently larger than a given number only depending on γ, then χγ(G)≤M-1. By means of the spectral radius λ1(G) of the adjacency matrix of G, it was shown that χ2(G) ≤ λ1(G)2+1, where the equality holds if and only if G is a star or a Moore graph with diameter 2 and girth 5, and χγ(G) < λ1(G)γ+1 if γ≥ 3.