Edge-switching homomorphisms of edge-coloured graphs

An edge-coloured graph G is a vertex set V(G) together with m edge sets distinguished by m colours. Let pi be a permutation on {1, 2,...,m). We define a switching operation consisting of pi acting on the edge colours similar to Seidel switching, to switching classes as studied by Babai and Cameron, and to the pushing operation studied by Klostermeyer and MacGillivray. An edge-coloured graph G is pi-permutably homomorphic (respectively pi-permutably isomorphic) to an edge-coloured graph H if some sequence of switches on G produces an edge-coloured graph homomorphic (respectively isomorphic) to H. We Study the pi-homomorphism and pi-isomorphism operations, relating them to homomorphisms and isomorphisms of a constructed edge-coloured graph that we introduce called a colour switching graph. Finally, we identify those edge-coloured graphs H with the property that G is homomorphic to H if and only if any switch of G is homomorphic to H. It turns out that such an H is precisely a colour switching graph. As a corollary to our work, we settle an open problem of Klostermeyer and MacGillivray. (C) 2008 Elsevier B.V. All rights reserved.