Distinguishing infinite graphs with bounded degrees
classification
🧮 math.CO
keywords
distinguishingcolouringdeltagraphautomorphismconjecturedegreegraphs
read the original abstract
Call a colouring of a graph distinguishing, if the only colour preserving automorphism is the identity. A conjecture of Tucker states that if every automorphism of a graph $G$ moves infinitely many vertices, then there is a distinguishing $2$-colouring. We confirm this conjecture for graphs with maximum degree $\Delta \leq 5$. Furthermore, using similar techniques we show that if an infinite graph has maximum degree $\Delta \geq 3$, then it admits a distinguishing colouring with $\Delta - 1$ colours. This bound is sharp.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.