THE EXISTENCE OF HOMOMORPHISMS TO ORIENTED CYCLES

We discuss the existence of homomorphisms of arbitrary digraphs to a fixed oriented cycle C. Our main result asserts that if the cycle C is unbalanced then a digraph G is homomorphic to C if and only if (1) every oriented path homomorphic to G is also homomorphic to C, and (2) the length of every cycle of G is a multiple of the length of C. This answers a conjecture from an earlier paper with H. Zhou and generalizes a result proved there. We also show that this characterization does not hold for balanced cycles. We relate these results to work on the complexity of homomorphism problems.