2018/10/09 by Lehner, Florian, Pilśniak, Monika, Stawiski, Marcin
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1810.03932
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 Δ≤ 5. Furthermore, using similar techniques we show that if an infinite graph has maximum degree Δ≥ 3, then it admits a distinguishing colouring with Δ- 1 colours. This bound is sharp.