2018/07/03 by Lehner, Florian, Smith, Simon M. · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1807.01116
Let c and c' be edge or vertex colourings of a graph G. We say that c' is less symmetric than c if the stabiliser (in Aut G) of c' is contained in the stabiliser of c. We show that if G is not a bicentred tree, then for every vertex colouring of G there is a less symmetric edge colouring with the same number of colours. On the other hand, if T is a tree, then for every edge colouring there is a less symmetric vertex colouring with the same number of edges. Our results can be used to characterise those graphs whose distinguishing index is larger than their distinguishing number.