← All problems

Tucker's infinite motion conjecture for locally finite graphs

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

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

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.