The 2-colouring problem for (m; n)-mixed graphs with switching is polynomial

A mixed graph is a set of vertices together with an edge set and an arc set. An (m; n)-mixed graph G is a mixed graph whose edges are each assigned one of m colours, and whose arcs are each assigned one of n colours. A switch at a vertex v of G permutes the edge colours, the arc colours, and the arc directions of edges and arcs incident with v. The group of all allowed switches is Gamma. Let k >= 1 be a fixed integer and Gamma a fixed permutation group. We consider the problem that takes as input an (m, n)-mixed graph G and asks if there is a sequence of switches at vertices of G with respect to Gamma so that the resulting (m, n)-mixed graph admits a homomorphism to an (m; n)-mixed graph on k vertices. Our main result establishes that this problem can be solved in polynomial time for k <= 2, and is NP-hard for k >= 3. This provides a step towards a general dichotomy theorem for the Gamma-switchable homomorphism decision problem.