2
$\begingroup$

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?

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks! And this example also seems will work even if we were to consider the action of $\mathop{Aut}(\Gamma)$ on $\mathcal{C}$. $\endgroup$ May 1, 2019 at 1:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .