A bound for the distinguishing index of regular graphs

DOI10.1016/J.EJC.2020.103145MaRDI QIDQ2198979zbMATH OpenOpenAlexFDO

Authors Florian Lehner, Monika Pilśniak, Marcin Stawiski

Publication date 15 September 2020

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

distinguishing edge-colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: An edge-colouring of a graph is distinguishing, if the only automorphism which preserves the colouring is the identity. It has been conjectured that all but finitely many connected, finite, regular graphs admit a distinguishing edge-colouring with two colours. We show that all such graphs except $K_2$ admit a distinguishing edge-colouring with three colours. This result also extends to infinite, locally finite graphs. Furthermore, we are able to show that there are arbitrary large infinite cardinals $kappa$ such that every connected $kappa$-regular graph has distinguishing edge-colouring with two colours.

Recommendations

• Distinguishing graphs by edge-colourings
• Breaking graph symmetries by edge colourings
• Bounds for distinguishing invariants of infinite graphs
• The distinguishing index of infinite graphs
• The optimal general upper bound for the distinguishing index of infinite graphs

Cites work

• Asymmetric trees with two prescribed degrees
• Breaking graph symmetries by edge colourings
• Distinguishing colorings of Cartesian products of complete graphs
• Distinguishing graphs by edge-colourings
• Distinguishing index of maps
• Improving upper bounds for the distinguishing index
• Set Theory
• Symmetry breaking in graphs
• The distinguishing index of infinite graphs
• The distinguishing index of the Cartesian product of countable graphs
• The distinguishing index of the Cartesian product of finite graphs
• The distinguishing number of Cartesian products of complete graphs
• The optimal general upper bound for the distinguishing index of infinite graphs

Cited in

(20)

• Bounds for distinguishing invariants of infinite graphs
• On colour-blind distinguishing colour pallets in regular graphs
• On symmetries of edge and vertex colourings of graphs
• Random colourings and automorphism breaking in locally finite graphs
• Distinguishing index of graphs with simple automorphism groups
• The role of the Axiom of Choice in proper and distinguishing colourings
• The distinguishing index of connected graphs without pendant edges
• The distinguishing index of graphs with infinite minimum degree
• Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's conjecture confirmed
• Distinguishing infinite graphs with bounded degrees
• Edge-determining sets and determining index
• Corrigendum to: ``A bound for the distinguishing index of regular graphs
• A note on breaking small automorphisms in graphs
• The distinguishing number and the distinguishing index of line and graphoidal graph(s)
• Distinguishing homomorphisms of infinite graphs
• Color-blind index in graphs of very low degree
• Distinguishing arc-colourings of symmetric digraphs
• Asymmetric edge-colorings of graphs with three colors
• Breaking graph symmetries by edge colourings
• Some bounds on the neighbor-distinguishing index of graphs

This page was built for publication: A bound for the distinguishing index of regular graphs

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