| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4649450 | Discrete Mathematics | 2009 | 7 Pages |
An edge-coloured graph GG is a vertex set V(G)V(G) together with mm edge sets distinguished by mm colours. Let ππ be a permutation on {1,2,…,m}{1,2,…,m}. We define a switching operation consisting of ππ 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 GG is ππ-permutably homomorphic (respectively ππ-permutably isomorphic) to an edge-coloured graph HH if some sequence of switches on GG produces an edge-coloured graph homomorphic (respectively isomorphic) to HH. We study the ππ-homomorphism and ππ-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 HH with the property that GG is homomorphic to HH if and only if any switch of GG is homomorphic to HH. It turns out that such an HH is precisely a colour switching graph. As a corollary to our work, we settle an open problem of Klostermeyer and MacGillivray.
