A dichotomy theorem for $\hat{I}“$-switchable $H$-colouring on $m$-edge coloured graphs

Abstract

Let $G$ be a graph in which each edge is assigned one of the colours $1,2,\dots ,m$, and let $\hat{I}“$ be a subgroup of $S_m$. The operation of switching at a vertex $x$ of $G$ with respect to an element $\ddot{I}€$ of $\hat{I}“$ permutes the colours of the edges incident with $x$ according to $\ddot{I}€$. We investigate the complexity of whether there exists a sequence of switches that transforms a given $m$-edge coloured graph $G$ so that it has a colour-preserving homomorphism to a fixed $m$-edge coloured graph $H$ and give a dichotomy theorem in the case that $\hat{I}“$ acts transitively.

17 pages, 2 figures