solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看4767次
Distinguishing infinite graphs with bounded degrees. (arXiv:1810.03932v1 [math.CO])
来源于:arXiv
Call a colouring of a graph distinguishing, if the only colour preserving
automorphism is the identity. A conjecture of Tucker states that if every
automorphism of a graph $G$ moves infinitely many vertices, then there is a
distinguishing $2$-colouring. We confirm this conjecture for graphs with
maximum degree $\Delta \leq 5$. Furthermore, using similar techniques we show
that if an infinite graph has maximum degree $\Delta \geq 3$, then it admits a
distinguishing colouring with $\Delta - 1$ colours. This bound is sharp. 查看全文>>