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{10_37236_4873,
author = {Florian Lehner and R\"ognvaldur G. M\"oller},
title = {Local finiteness, distinguishing numbers, and {Tucker's} conjecture},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {4},
doi = {10.37236/4873},
zbl = {1323.05050},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4873/}
}
TY - JOUR
AU - Florian Lehner
AU - Rögnvaldur G. Möller
TI - Local finiteness, distinguishing numbers, and Tucker's conjecture
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/4873/
DO - 10.37236/4873
ID - 10_37236_4873
ER -
%0 Journal Article
%A Florian Lehner
%A Rögnvaldur G. Möller
%T Local finiteness, distinguishing numbers, and Tucker's conjecture
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/4873/
%R 10.37236/4873
%F 10_37236_4873
Florian Lehner; Rögnvaldur G. Möller. Local finiteness, distinguishing numbers, and Tucker's conjecture. The electronic journal of combinatorics, Tome 22 (2015) no. 4. doi: 10.37236/4873
