A note on breaking small automorphisms in graphs

作者：Kalinowski Rafal^*; Pilsniak Monika; Wozniak Mariusz

来源：Discrete Applied Mathematics, 2017, 232: 221-225.

DOI：10.1016/j.dam.2017.07.034

• Symmetry breaking in graphs
• 1-2-3 Conjecture
• 1-2 Conjecture
• Distinguishing index
• Total distinguishing index

This paper brings together two concepts in the theory of graph colourings: edge or total colourings distinguishing adjacent vertices and those breaking symmetries of a graph.
We introduce a class of automorphisms such that edge colourings breaking them are connected to edge colouring distinguishing neighbours by multisets or sums. We call an automorphism of a graph G small if there exists a vertex of G that is mapped into its neighbour. The small distinguishing index of G, denoted D'(s)(G), is the least number of colours in an edge colouring of G such that there does not exist a small automorphism of G preserving this colouring. We prove that D'(s)(G) <= 3 for every graph G without K-2 as a component, thus supporting, in a sense, the 1-2-3 Conjecture of Karonski, Luczak and Thomason.
We also consider an analogous problem for total colourings in connection with the 1-2 Conjecture of Przybylo and Wozniak.

• 出版日期2017-12-11