Distinguishing infinite graphs with bounded degrees

DOI10.1002/JGT.22809MaRDI QIDQ6081887zbMATH OpenOpenAlexFDO

Authors Florian Lehner, Monika Pilśniak, Marcin Stawiski

Publication date 5 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.03932

zbMATH Keywords

asymmetric colouringdistinguishing number

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Infinite graphs (05C63)

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 graph $G$ moves infinitely many vertices, then there is a distinguishing $2$-colouring. We confirm this conjecture for graphs with maximum degree $Deltaleq5$. Furthermore, using similar techniques we show that if an infinite graph has maximum degree $Deltageq3$, then it admits a distinguishing colouring with $Delta-1$ colours. This bound is sharp.

Recommendations

• Local finiteness, distinguishing numbers, and Tucker's conjecture
• Bounds for distinguishing invariants of infinite graphs
• Distinguishing graphs with infinite motion and nonlinear growth
• A bound for the distinguishing index of regular graphs
• Breaking graph symmetries by edge colourings

Cites work

• A brief history of the classification of the finite simple groups
• Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's conjecture confirmed
• Asymmetric trees with two prescribed degrees
• Breaking graph symmetries by edge colourings
• Distinguishing graphs of maximum valence 3
• Distinguishing graphs with intermediate growth
• Distinguishing infinite graphs
• Distinguishing labellings of group action on vector spaces and graphs
• Distinguishing maps
• Distinguishing numbers of finite 4-valent vertex-transitive graphs
• Infinite motion and 2-distinguishability of graphs and groups
• Local finiteness, distinguishing numbers, and Tucker's conjecture
• On asymmetric colourings of claw-free graphs
• Random colourings and automorphism breaking in locally finite graphs
• The distinguishing chromatic number

Cited in

(20)

• On a theorem of Halin
• On asymmetric colourings of claw-free graphs
• Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's conjecture confirmed
• Distinguishing density and the distinct spheres condition
• Distinguishing graphs of maximum valence 3
• Bounds for distinguishing invariants of infinite graphs
• Distinguishing infinite graphs
• Distinguishing graphs with intermediate growth
• Bounded-degree graphs can have arbitrarily large slope numbers
• Distinguishing graphs with infinite motion and nonlinear growth
• Infinite graphs with finite 2-distinguishing cost
• Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
• Random colourings and automorphism breaking in locally finite graphs
• The role of the Axiom of Choice in proper and distinguishing colourings
• Asymmetric colouring of locally compact permutation groups
• On asymmetric colourings of graphs with bounded degrees and infinite motion
• Uniquely proper distinguishing colorable graphs
• Brooks' type theorems for coloring parameters of locally finite graphs and Kőnig's Lemma
• Distinguishing infinite star-free graphs
• Local finiteness, distinguishing numbers, and Tucker's conjecture

This page was built for publication: Distinguishing infinite graphs with bounded degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6081887)