The Distance Coloring of Graphs

Abstract

Let $G$ be a connected graph with maximum degree $\Delta \ge 3$. We investigate the upper bound for the chromatic number ${\chi }_{\gamma }(G)$ of the power graph $G^{\gamma }$. It was proved that ${\chi }_{\gamma }(G)\le \Delta \frac{(\Delta -1{)}^{\gamma }-1}{\Delta -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)\le 2\gamma -1$, (3) $g(G)\ge 2\gamma +2$, and the connectivity $\kappa (G)\ge 3$ if $\gamma \ge 3$, $\kappa (G)\ge 4$ but $g(G)>6$ if $\gamma =2$, (4) $\Delta$ is sufficiently large than a given number only depending on $\gamma$, then ${\chi }_{\gamma }(G)\le M-1$. By means of the spectral radius ${\lambda }_1(G)$ of the adjacency matrix of $G$, it was shown that ${\chi }_2(G)\le {\lambda }_1(G{)}^2+1$, with equality holds if and only if $G$ is a star or a Moore graph with diameter 2 and girth 5, and ${\chi }_{\gamma }(G)<{\lambda }_1(G{)}^{\gamma }+1$ if $\gamma \ge 3$.

Cited by in corpus (2)

• A Brooks-like result for graph powers
• Brooks' theorem on powers of graphs