Local finiteness, distinguishing numbers, and Tucker's conjecture

Link:
Autor/in:
Erscheinungsjahr:
2015
Medientyp:
Text
Schlagworte:
  • Distinguishing number
  • Infinite Graphs
Beschreibung:
  • 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.
Lizenz:
  • info:eu-repo/semantics/openAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/d61b11d0-ade5-4bd5-a969-01b0db4a875f