On homomorphisms to edge-coloured cycles

Given an edge-coloured graph H (a graph with the edges coloured, not necessarily by a proper colouring) the H-colouring problem asks whether or not an arbitrary edge-coloured graph G admits a homomorphism to H, i.e., a mapping of the vertices of G to the vertices of H which preserves edges and their colours. We study the complexity of the H-colouring problem when H is an edge coloured cycle. We identify a number of cases when the problem is polynomial time solvable and a family of NP-complete problems In particular, we completely classify the complexity when H has at most six runs (maximal monochromatic paths). We also present evidence that a complete classification of the complexity of this problem is likely to be difficult to obtain.