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
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.
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).
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.