×

On homomorphisms to edge-coloured cycles. (English) Zbl 1412.05064

Rusu, Irena (ed.), Proceedings of the 6th international conference on graph theory, Marseille-Luminy, France, August 28–September 2, 2000. Amsterdam: Elsevier. Electron. Notes Discrete Math. 5, 46-49 (2000).
Summary: 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.
For the entire collection see [Zbl 0974.00033].

MSC:

05C15 Coloring of graphs and hypergraphs
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: Link