The Distance Coloring of Graphs

Let $G$ be a connected graph with maximum degree $\mathrm{\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$,andtheconnectivity$\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$.