The Existence of Homomorphisms to Oriented Cycles

Abstract

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.