Hell, Pavol; Zhu, Xuding The existence of homomorphisms to oriented cycles. (English) Zbl 0831.05059 SIAM J. Discrete Math. 8, No. 2, 208-222 (1995). Let \(G\) and \(H\) be finite digraphs. A homomorphism \(f : G \to H\) is a mapping of the vertex sets such that if \(xy\) is an arc of \(G\) then \(f(x) f(y)\) is an arc of \(H\). An oriented path \(P\) is a graph with vertex set \(\{p_0, p_1, \ldots, p_m\}\) such that for all \(i = 0, \ldots, m - 1\) either \(p_i p_{i + 1}\) (forward) or \(p_i p_{i - 1}\) (backward) is an arc, and \(P\) has no other arcs. The length of \(P\) is the number of forward arcs minus that of backward arcs. An oriented cycle \(C\) is defined as above, but \(p_0 = p_m\). The \(H\)-coloring problem is to decide whether there is a homomorphism from \(G\) to \(H\). For undirected graphs, this decision problem is polynomial for bipartite \(H\) and NP- complete otherwise (see [P. Hell and J. Nešestřil, J. Comb. Theory, Ser. B 48, No. 1, 92-110 (1990; Zbl 0639.05023)]). The directed case cannot have such a simple answer, because for both polynomial and NP-complete there are many examples (see e.g. [G. S. Bloom and S. A. Burr, J. Graph Theory 11, No. 4, 453-462 (1987; Zbl 0647.05025)], [W. Gutjahr, E. Welzl and G. Woeginger, Discrete Appl. Math. 35, No. 1, 29-46 (1992; Zbl 0761.05040)] and [G. McGillivray, SIAM J. Discrete Math. 4, No. 3, 397-408 (1991; Zbl 0735.68042)]). It is proved that if \(C\) is a cycle of length different from zero then a digraph \(G\) is homomorphic to \(C\) if and only if (1) every oriented path homomorphic to \(G\) is homomorphic to \(C\), and (2) the length of every cycle of \(G\) is a multiple of that of \(C\). It is also shown that this does not hold for cycles of length zero. The link of the above results with computational complexity is also discussed. Reviewer: R.Scapellato (Milano) Cited in 11 Documents MSC: 05C99 Graph theory 05C20 Directed graphs (digraphs), tournaments 05C38 Paths and cycles Keywords:digraphs; homomorphism; oriented path; forward arcs; backward arcs; oriented cycle; NP-complete; computational complexity Citations:Zbl 0639.05023; Zbl 0679.05032; Zbl 0647.05025; Zbl 0761.05040; Zbl 0735.68042 PDFBibTeX XMLCite \textit{P. Hell} and \textit{X. Zhu}, SIAM J. Discrete Math. 8, No. 2, 208--222 (1995; Zbl 0831.05059) Full Text: DOI