
Let $G$ be a connected graph with maximum degree $��\ge 3$. We investigate the upper bound for the chromatic number $��_��(G)$ of the power graph $G^��$. It was proved that $��_��(G) \le��\frac{(��-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) \le 2��-1$, (3) $g(G) \ge 2��+2$, and the connectivity $��(G) \ge 3$ if $��\ge 3$, $��(G) \ge 4$ but $g(G) >6$ if $��=2$, (4) $��$ is sufficiently large than a given number only depending on $��$, then $��_��(G) \le M-1$. By means of the spectral radius $��_1(G)$ of the adjacency matrix of $G$, it was shown that $��_2(G) \le ��_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 $��_��(G) < ��_1(G)^��+1$ if $��\ge 3$.
FOS: Mathematics, Mathematics - Combinatorics, 05C15, 05C50, Combinatorics (math.CO)
FOS: Mathematics, Mathematics - Combinatorics, 05C15, 05C50, Combinatorics (math.CO)
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 6 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
