A bound for the distinguishing index of regular graphs

Florian Lehner; Monika Pilśniak; Marcin Stawiski

doi:10.1016/j.ejc.2020.103145

paper

A bound for the distinguishing index of regular graphs

arXiv:1911.11105 · doi:10.1016/j.ejc.2020.103145

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 $κ$ such that every connected $κ$ -regular graph has distinguishing edge-colouring with two colours.