On symmetries of edge and vertex colourings of graphs

Abstract

Let $c$ and $c^{\prime }$ be edge or vertex colourings of a graph $G$. We say that $c^{\prime }$ is less symmetric than $c$ if the stabiliser (in $\mathrm{Aut}G$) of $c^{\prime }$ 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.

13 Pages