Local Finiteness, Distinguishing Numbers, and Tucker's Conjecture

  • Florian Lehner
  • Rögnvaldur G. Möller
Keywords: Distinguishing number, Infinite Graphs


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.
Article Number