For any finite, simple, undirected graphs $G, H$ we denote by $G\times H$ their [categorical product](https://en.wikipedia.org/wiki/Tensor_product_of_graphs). 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](https://en.wikipedia.org/wiki/Computable_function) for finite graphs?



The sequence of the power chromatic numbers $(\chi(G^n))_{n\in\mathbb{N}}$
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.


