Tucker's infinite motion conjecture for locally finite graphs
Let be a connected, locally finite graph. The motion of is
where is the cardinality of the set of vertices not fixed by . The graph has infinite motion when is infinite.
Infinite motion conjecture. If is a connected, locally finite graph with infinite motion, then
This conjecture proposes that every connected, locally finite graph whose nontrivial automorphisms move infinitely many vertices admits a distinguishing vertex coloring with two colors. The paper proves the conjecture under additional hypotheses, but the general statement is presented as an open problem.
References
Primary source
Jesús Antonio Álvarez López, Ramón Barral Lijó and Hiraku Nozawa, “Coarse distinguishability of graphs with symmetric growth”, arXiv:2005.09716 (2020).
Additional references
5 papers in this index state this conjecture (2013–2020). The statement above is taken from the most recent of them; the others are arXiv:1810.03932, arXiv:1604.08144, arXiv:1304.6642, arXiv:1301.0393.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.