×

The existence of homomorphisms to oriented cycles. (English) Zbl 0831.05059

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.

MSC:

05C99 Graph theory
05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI