Local finiteness, distinguishing numbers and Tucker's conjecture
A distinguishing colouring of a graph is a colouring of the vertex set such that no non-trivial
automorphism preserves the colouring. Tucker conjectured that if every non-trivial
automorphism of a locally finite graph moves infinitely many vertices, then there is a
distinguishing 2-colouring. We show that the requirement of local finiteness is necessary by
giving a non-locally finite graph for which no finite number of colours suffices.
automorphism preserves the colouring. Tucker conjectured that if every non-trivial
automorphism of a locally finite graph moves infinitely many vertices, then there is a
distinguishing 2-colouring. We show that the requirement of local finiteness is necessary by
giving a non-locally finite graph for which no finite number of colours suffices.
A distinguishing colouring of a graph is a colouring of the vertex set such that no non-trivial automorphism preserves the colouring. Tucker conjectured that if every non-trivial automorphism of a locally finite graph moves infinitely many vertices, then there is a distinguishing 2-colouring. We show that the requirement of local finiteness is necessary by giving a non-locally finite graph for which no finite number of colours suffices.
arxiv.org