pith. sign in

arxiv: 1810.03932 · v1 · pith:MTSVA66Rnew · submitted 2018-10-09 · 🧮 math.CO

Distinguishing infinite graphs with bounded degrees

classification 🧮 math.CO
keywords distinguishingcolouringdeltagraphautomorphismconjecturedegreegraphs
0
0 comments X
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.