Coloring infinite graph made out of copies of a finite graph

Question

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

1. Vertex set of $G^\infty$ is $$V(G^\infty) = \bigcup_{i \in \mathbb{Z}} V(G_i)$$
2. 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:

1. 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)})$
2. Color joined graph with greedy coloring
3. 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?

Answer 1

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.