A dichotomy theorem for \Gamma-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, l d o t s, m

, and let

G a m m a

be a subgroup of

S_{m}

. The operation of switching at a vertex

x

of

G

with respect to an element

p i

of

G a m m a

permutes the colours of the edges incident with

x

according to

p 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

G a m m a

acts transitively.

This page was built for publication: A dichotomy theorem for $\Gamma$-switchable $H$-colouring on $m$-edge coloured graphs