# Cardinality of minimal edge-colourings of an infinite vertex-transitive graph

Let $$\Gamma$$ be a an infinite simplicial graph, i.e. $$V\Gamma$$ is a set and $$E\Gamma \subseteq \binom{V\Gamma}{2}$$ - $$\Gamma$$ is unoriented and does not contain loops and multiple edges, and let $$G$$ denote the group of automorphisms of $$\Gamma$$. Suppose that $$\Gamma$$ is locally finite, connected and vertex transitive, meaning that for every pair of vertices $$u,v \in V\Gamma$$ there is an automorphism $$g \in G$$ such that $$g(u) = v$$. It follows that all vertices are of the same degree, say $$d$$.

Following Vizing's theorem, every finite subgraph of $$\Gamma$$ has edge-colouring with $$d+1$$ colours and then by de Bruijn–Erdős theorem the whole graph $$\Gamma$$ has an edge colouring using up to $$d+1$$ colours. Let $$c \in \{d, d+1\}$$ be the edge-chromatic number and let $$\mathcal{C} \subseteq \{\lambda \colon E\Gamma \to \{1, \dots, c\}\}$$ denote the set of all $$c$$-colourings of $$\Gamma$$.

My question is following: is the set $$\mathcal{C}$$ finite? I can see that in the case when $$\Gamma$$ is not vertex transitive, the answer is negative, similarly if we allow non-optimal colourings.

EDIT: The set $$\mathcal{C}$$ will very often be (uncountably) infinite, as pointed out in the comments, so a better thing to ask is: is the number of orbits of $$\mathcal{C}$$ under the action of $$\mathop{Aut}(\Gamma)$$ finite, provided we are allowing only optimal colourings?

• The $3$-regular tree has $2^{\aleph_0}$ proper edge-colourings with $3$ colours.
– bof
Apr 29, 2019 at 23:52

Let $$\Gamma$$ be an infinite square grid. Then $$c=4$$ and $$|\mathcal C|=\frak c$$. To show this for each map $$f:\Bbb Z\to \{0,1\}$$ we present a coloring $$\chi_f$$ of edges of $$\Gamma$$ such that each vertical edge $$\{(i,j),(i,j+1)\}$$ is colored in $$1$$ if $$j$$ is odd and is colored in $$2$$, otherwise and each horizontal edge $$\{(i,j),(i+1,j)\}$$ is colored in $$3$$ if $$i+\chi_f$$ is odd and is colored in $$4$$, otherwise. It is easy to see that a map $$f\to\chi_f$$ is injective.
• Thanks! And this example also seems will work even if we were to consider the action of $\mathop{Aut}(\Gamma)$ on $\mathcal{C}$. May 1, 2019 at 1:35