Colour-permuting and colour-preserving automorphisms

PLENARY TALK

Content: A Cayley graph Cay$(G;S)$ on a group $G$ with connection set $S=S^{-1}$ is the graph whose vertices are the elements of $G$, with $g \sim h$ if and only if $g^{-1}h \in S$. If we assign a colour $c(s)$ to each $s \in S$ so that $c(s)=c(s^{-1})$ and $c(s)\neq c(s')$ when $s' \neq s, s^{-1}$, this is a natural (but not proper) edge-colouring of the Cayley graph. The most natural automorphisms of any Cayley graph are those that come directly from the group structure: left-multiplication by any element of $G$; and group automorphisms of $G$ that fix $S$ setwise. It is easy to see that these graph automorphisms either preserve or permute the colours in the natural edge-colouring defined above. Conversely, we can ask: if a graph automorphism preserves or permutes the colours in this natural edge colouring, need it come from the group structure in one of these ways? We show that in general, the answer to this question is no. We explore the answer to this question for a variety of families of groups and of Cayley graphs on these groups. I will touch on work by other authors that explores similar questions coming from closely-related colourings.

Back to all abstracts