Premium
Distinguishing infinite graphs with bounded degrees
Author(s) -
Lehner Florian,
Pilśniak Monika,
Stawiski Marcin
Publication year - 2022
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22809
Subject(s) - mathematics , combinatorics , conjecture , bounded function , automorphism , graph , vertex transitive graph , discrete mathematics , degree (music) , graph automorphism , line graph , graph power , voltage graph , mathematical analysis , physics , acoustics
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 graphG $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.