Coloring infinite graph made out of copies of a finite graph I have an infinite graph $G^\infty$ constructed out of sequence $G_t$ of copies of some finite graph $G$. More specifically:

*

*Vertex set of $G^\infty$ is $$V(G^\infty) = \bigcup_{i \in \mathbb{Z}} V(G_i)$$

*Edge set of $G^\infty$ is $$E(G^\infty) = \bigcup_{i \in \mathbb{Z}} \left( E(G_i) \cup  \bigcup_{j = 1}^K \hat{E}_j(G_i, G_{i+j}) \right)$$
Where $\hat{E}_j(G_i, G_{i+j})$ is arbitrary set of edges between vertices of $G_i$ and $G_{i+j}$ and $K$ is some finite constant. Note that $\hat{E}_j$ doesn't depend on $i$, so $G^\infty$ has a regular structure.

I want to find a good proper vertex coloring of such graph. So far I found the following simple algorithm:

*

*Join $G_0, \ldots, G_{K}$ graphs circularly by replacing $\hat{E}_j(G_i, G_{i+j})$ with $\hat{E}_j(G_i, G_{(i+j)\ \mathrm{mod}\ (K+1)})$

*Color joined graph with greedy coloring

*To color $G_i$ from $G^\infty$ use coloring of $G_{i\ \mathrm{mod}\ (K+1)}$ from joined graph

But I think a better coloring algorithm can be found. So the question is there any known coloring algorithms for these types of graphs? And do these types of graphs has a common name and mentioned in literature?
 A: Here is how to reduce the problem to a finite colouring problem.
Let $G'=G_0 \cup \dots \cup G_K$. For each $t \in \mathbb{N}$, the $tG'$ be the subgraph of $G^\infty$ consisting of $t$ consecutive copies of $G'$.
Claim. For all $t \in \mathbb{N}$, $\chi(tG') \leq 2\chi(G')$.
Proof.
Partition $V(tG')$ into even and odd sets where each set induces a copy of $G'$. Then use $\chi(G')$ colours on the even copies of $G'$ and a different set of $\chi(G')$ colours on the odd copies of $G'$.
Claim. There exists an (explicitly defined) $t$ such that $\chi(tG')=\chi(G^\infty)$.
Proof. Since the chromatic number of $tG'$ is bounded for all $t$, there exists $t \geq 2$ such that the first and last copy of $G'$ are coloured exactly the same in an optimal colouring of $tG'$.  This allows us to extend such a colouring of $tG'$ to a colouring of $G^\infty$.
The above proof is constructive and allows us to find $t$ explicitly, and to compute the optimal colouring of $G^\infty$ in constant time.  By the De Bruijn–Erdős theorem, we know that such a $t$ always exists.
