Projects per year
Let c and c ′ be edge or vertex colourings of a graph G. The stabiliser of c is the set of automorphisms of G that preserve the colouring. We say that c ′ is less symmetric than c if the stabiliser 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 colours. Our results can be used to characterise those graphs whose distinguishing index is larger than their distinguishing number.
|Number of pages||8|
|Publication status||Published - 2020|
- Distinguishing index
- Distinguishing number
- Graph automorphism
- Graph colouring
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
Fields of Expertise
- Information, Communication & Computing
FingerprintDive into the research topics of 'On symmetries of edge and vertex colourings of graphs'. Together they form a unique fingerprint.
- 1 Finished