1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Yes, this is correct. I edited question with clarifications $\endgroup$ Jul 3, 2021 at 9:23

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ $(K+1)\chi(G)$ seems to be not an optimal chromatic number but an upper bound. Because consider $G$ to be a single isolated node, $K=2$, $\hat{E_1} = \varnothing$ and $\hat{E_2}$ to connect two isolated nodes. Then $\chi(G)$ = 1 but $\chi(G^\infty)=2$, not $(K+1)\chi(G) = 3$ $\endgroup$ Jul 3, 2021 at 7:09
  • $\begingroup$ I interpreted your question to mean that $\hat{E}_j$ is a complete bipartite graph for all $j$. I edited my answer accordingly. $\endgroup$
    – Tony Huynh
    Jul 3, 2021 at 8:13
  • $\begingroup$ How do you preserve coloring consistency between even and odd coloring, when "joining" one to another? $\endgroup$ Jul 3, 2021 at 8:57
  • $\begingroup$ Since we use disjoint sets of colours on the even and odd copies, there is no issue between even and odd copies. Since there are no edges between two even copies (or between two odd copies), there are no consistency issues between those copies either. $\endgroup$
    – Tony Huynh
    Jul 3, 2021 at 9:00
  • $\begingroup$ Oh, I missed the disjoint part, sorry. $2\chi(G')$ is a bound I was thinking about too. Also my algorithm in the question above gives $|G'|$ bound, which sometimes can be lower than $2\chi(G')$. But I was wondering, if there any smarter method to color these graphs to get some kind of $\chi(G') + O(1)$ bound? $\endgroup$ Jul 3, 2021 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.