The Distance Coloring of Graphs

Original · EN

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 with equality if and only G is a Moore graph. If G is not a Moore graph, and G holds 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(G) >6 if γ=2, (4) Δ is sufficiently large than a given number only depending on γ, then χγ(G) ≤ M-1. By means of the spectral radius λ₁(G) of the adjacency matrix of G, it was shown that χ₂(G) ≤ λ₁(G)²+1, with equality holds if and only if G is a star or a Moore graph with diameter 2 and girth 5, and χγ(G) < λ₁(G)γ+1 if γ≥ 3.