The sequence of the power chromatic numbers $(\chi(G^n))_{n\in\mathbb{N}}$

Question

For any finite, simple, undirected graphs $G, H$ we denote by $G\times H$ their categorical product. For any graph $G$ we let $G^1 = G$ and for $n\geq 1$ we let $G^{n+1} = G \times G^n$.

It is easy to see that the sequence of the power chromatic numbers $(\chi(G^n))_{n\in\mathbb{N}}$ is decreasing and so it is eventually constant with a unique value we denote by $\chi^\infty(G)$.

Question. Is $\chi^\infty(G)$ computable for finite graphs?

Answer 1

Yes.

First note that $\chi(G^k) \leq \chi(G)$. We can colour $(x_1, \ldots, x_k)$ with $c(x_1)$ where $c$ is a colouring of $G$.

Vice versa $\chi(G^k) \geq \chi(H) = \chi(G)$, where $H$ is the induced subgraph of $G^k$ on the vertices $\{(v, v, \ldots, v) \mid v \in V(G)\}$.

Thus $\chi(G^k) = \chi(G)$, which is computable.