Duality Pairs and Homomorphisms to Oriented and Unoriented Cycles
Duality Pairs and Homomorphisms to Oriented and Unoriented Cycles
In the homomorphism order of digraphs, a duality pair is an ordered pair of digraphs $(G,H)$ such that for any digraph, $D$, $G\to D$ if and only if $D\not \to H$. The directed path on $k+1$ vertices together with the transitive tournament on $k$ vertices is a classic example of …