Tucker's infinite motion conjecture for locally finite graphs

About 13 years old · traced to

Let XX be a connected, locally finite graph. The motion of XX is

m(X)=inf⁡{m(f)∣f∈Aut⁡(X), f≠id⁡},m(X)=\inf\{m(f)\mid f\in\operatorname{Aut}(X),\ f\neq\operatorname{id}\},

where m(f)m(f) is the cardinality of the set of vertices not fixed by ff. The graph XX has infinite motion when m(X)m(X) is infinite.

Infinite motion conjecture. If XX is a connected, locally finite graph with infinite motion, then

D(X)≤2.D(X)\leq 2.

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

Never refreshed

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.