Breaking graph symmetries by edge colourings

DOI10.1016/J.JCTB.2017.06.001MaRDI QIDQ2407385zbMATH OpenOpenAlexFDO

Authors Florian Lehner

Publication date 29 September 2017

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

automorphism groupdistinguishing indexdistinguishing numberinfinite graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Infinite graphs (05C63)

Abstract: The distinguishing index $D^{\prime }(G)$ of a graph $G$ is the least number of colours needed in an edge colouring which is not preserved by any non-trivial automorphism. Broere and Pil'sniak conjectured that if every non-trivial automorphism of a countable graph $G$ moves infinitely many edges, then $D^{\prime }(G)leq2$. We prove this conjecture.

Recommendations

• Distinguishing graphs by edge-colourings
• A bound for the distinguishing index of regular graphs
• The distinguishing index of connected graphs without pendant edges
• The distinguishing index of infinite graphs
• Distinguishing index of graphs with simple automorphism groups

Cites work

• A note on the asymptotic and computational complexity of graph distinguishability
• Distinguishability of infinite groups and graphs
• Distinguishability of locally finite trees
• Distinguishing graphs by edge-colourings
• Distinguishing graphs with infinite motion and nonlinear growth
• Distinguishing graphs with intermediate growth
• Distinguishing infinite graphs
• Distinguishing maps
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Infinite motion and 2-distinguishability of graphs and groups
• Local finiteness, distinguishing numbers, and Tucker's conjecture
• Random colourings and automorphism breaking in locally finite graphs
• Symmetry breaking in graphs
• The distinguishing index of infinite graphs
• Zu einem Isomorphiesatz von H. Whitney für Graphen

Cited in

(27)

• Methods of destroying the symmetries of a graph
• On asymmetric colourings of claw-free graphs
• The distinguishing number and distinguishing chromatic number for posets
• Extremal graphs for the distinguishing index
• Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's conjecture confirmed
• Trees with distinguishing index equal distinguishing number plus one
• A bound for the distinguishing index of regular graphs
• Distinguishing index of graphs with simple automorphism groups
• New algorithm for calculating chromatic index of graphs and its applications
• The distinguishing index of infinite graphs
• Bounds for distinguishing invariants of infinite graphs
• A note on breaking small automorphisms in graphs
• Asymmetric edge-colorings of graphs with three colors
• Nordhaus-Gaddum type inequalities for the distinguishing index
• Endomorphism breaking in graphs
• Distinguishing graphs by edge-colourings
• The distinguishing index of connected graphs without pendant edges
• Number of colors needed to break symmetries of a graph by an arbitrary edge coloring
• Symmetry-driven network reconstruction through pseudobalanced coloring optimization
• Random colourings and automorphism breaking in locally finite graphs
• Distinguishing infinite graphs with bounded degrees
• Asymmetric colouring of locally compact permutation groups
• The distinguishing index of graphs with infinite minimum degree
• Breaking small automorphisms by list colourings
• On asymmetric colourings of graphs with bounded degrees and infinite motion
• On symmetries of edge and vertex colourings of graphs
• Local finiteness, distinguishing numbers, and Tucker's conjecture

This page was built for publication: Breaking graph symmetries by edge colourings

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