Local finiteness, distinguishing numbers, and Tucker’s conjecture

Florian Lehner, Rögnvaldur G. Möller

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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.

Original languageEnglish
Article numberP4.19
JournalElectronic Journal of Combinatorics
Issue number4
Publication statusPublished - 30 Oct 2015

Bibliographical note

Publisher Copyright:
© 2015 Australian National University. All rights reserved.

Other keywords

  • Distinguishing number
  • Infinite Graphs


Dive into the research topics of 'Local finiteness, distinguishing numbers, and Tucker’s conjecture'. Together they form a unique fingerprint.

Cite this