Tucker's two-colour conjecture for connected locally finite graphs
Tucker's two-colour conjecture for connected locally finite graphs
Let be a connected, locally finite graph. The graph has infinite motion if every non-identity automorphism moves infinitely many vertices. A vertex colouring is asymmetric if the only automorphism preserving it is the identity. Tucker's conjecture. If has infinite motion, then there is an asymmetric colouring of with colours.
Despite numerous partial results, this conjecture remains wide open in general; it is a proposed infinite-graph analogue of the Motion Lemma for finite graphs.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Florian Lehner, Monika Pilśniak and Marcin Stawiski, “On asymmetric colourings of graphs with bounded degrees and infinite motion”, arXiv:1912.02560 (2020).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.