A bound for the distinguishing index of regular graphs

DOI10.1016/J.EJC.2020.103145zbMATH Open1447.05087arXiv1911.11105OpenAlexW2990585088MaRDI QIDQ2198979FDOQ2198979

Authors: Florian Lehner, Monika Pilśniak, Marcin Stawiski 

Publication date: 15 September 2020

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

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.

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

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

zbMATH Keywords

distinguishing edge-colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

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

Cited In (20)

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

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)