2019/12/05 by Florian Lehner, Lehner, Florian, Monika Pilśniak +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1912.02560
openalex publication_date 2019/12/05 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
A vertex colouring of a graph is called asymmetric if the only automorphism which preserves it is the identity. Tucker conjectured that if every automorphism of a connected, locally finite graph moves infinitely many vertices, then there is an asymmetric colouring with 2 colours. We make progress on this conjecture in the special case of graphs with bounded maximal degree. More precisely, we prove that if every automorphism of a connected graph with maximal degree Δ moves infinitely many vertices, then there is an asymmetric colouring using \mathcal O(√ Δlog Δ) colours. This is the first improvement over the trivial bound of \mathcal O(Δ).