# zbMATH — the first resource for mathematics

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
Full Text: