A bound for the distinguishing index of regular graphs. (October 2020)

• Record Type: Journal Article
• Authors: Lehner, Florian; Pilśniak, Monika; Stawiski, Marcin
• Is Part Of: European journal of combinatorics. Volume 89(2020)
• Publication Date: 2020-10
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2020.103145
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: An edge-colouring of a graph is distinguishing if the only automorphism that 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 a distinguishing edge-colouring with two colours.