The Library
Distinguishing infinite graphs with bounded degrees
Tools
Lehner, Florian, Pilśniak, Monika and Stawiski, Marcin (2022) Distinguishing infinite graphs with bounded degrees. Journal of Graph Theory, 101 (1). pp. 52-65. doi:10.1002/jgt.22809 ISSN 0364-9024.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: https://doi.org/10.1002/jgt.22809
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 moves infinitely many vertices, then there is a distinguishing 2-colouring. We confirm this conjecture for graphs with maximum degree Δ≤5 . Furthermore, using similar techniques we show that if an infinite graph has maximum degree Δ≥3 , then it admits a distinguishing colouring with Δ−1 colours. This bound is sharp.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
SWORD Depositor: | Library Publications Router | ||||||||
Journal or Publication Title: | Journal of Graph Theory | ||||||||
Publisher: | John Wiley & Sons Ltd. | ||||||||
ISSN: | 0364-9024 | ||||||||
Official Date: | September 2022 | ||||||||
Dates: |
|
||||||||
Volume: | 101 | ||||||||
Number: | 1 | ||||||||
Page Range: | pp. 52-65 | ||||||||
DOI: | 10.1002/jgt.22809 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |