Tucker's two-colour conjecture for connected locally finite graphs

From papers

Let GG be a connected, locally finite graph. The graph GG 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 GG has infinite motion, then there is an asymmetric colouring of GG with 22 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

No solutions have been posted yet.