2014/12/02 by Florian Lehner, Lehner, Florian, Rögnvaldur G. Möller +1
Computer Science · Engineering · Mathematics · #05C15 (Secondary) #05C25 (Primary) #05C63 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems #math.CO #msc:05C15 #msc:05C25 #msc:05C63
paper · pdf · doi:10.48550/arxiv.1412.0881
openalex publication_date 2014/12/02 · arxiv created 2015/04/29 · arxiv updated 2015/04/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.