Switching $(m,n)$-mixed graphs with respect to Abelian groups

Abstract

We extend results of Brewster and Graves for switching $m$-edge coloured graphs with respect to a cyclic group to switching $(m,n)$-mixed graphs with respect to an Abelian group. In particular, we establish the existence of a $(m,n)$-mixed graph $P_{\Gamma }(H)$ with the property that a $(m,n)$-mixed graph $G$ is switch equivalent to $H$ if and only if it is a special subgraph of $P_{\Gamma }(H)$, and the property that that $G$ can be switched to have a homomorphism to $H$ if and only if it has a homomorphism (without switching) to $P_{\Gamma }(H)$. We consider the question of deciding whether a $(m,n)$-mixed graph can be switched so that it has a homomorphism to a proper subgraph, i.e. whether it can be switched so that it isn't a core. We show that this question is NP-hard for arbitrary groups and NP-complete for Abelian groups. Finally, we consider the complexity of the switchable $k$-colouring problem for $(m,n)$-mixed graphs and prove a dichotomy theorem in the cases where $m\ge 1$.