Distinguishing infinite graphs with bounded degrees. Issue 1 (9th February 2022)

• Record Type: Journal Article
• Authors: Lehner, Florian; Pilśniak, Monika; Stawiski, Marcin
• Is Part Of: Journal of graph theory. Volume 101:Issue 1(2022)
• Page Start: 52
• Page End: 65
• Publication Date: 2022-02-09
• Subjects: asymmetric colouring -- distinguishing number; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22809
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: 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 connected graph G $G$ moves infinitely many vertices, then there is a distinguishing 2‐colouring. We confirm this conjecture for graphs with maximum degree Δ ≤ 5 ${\rm{\Delta }}\le 5$ . Furthermore, using similar techniques we show that if an infinite graph has maximum degree Δ ≥ 3 ${\rm{\Delta }}\ge 3$, then it admits a distinguishing colouring with Δ − 1 ${\rm{\Delta }}-1$ colours. This bound is sharp.