Duality pairs and homomorphisms to oriented and unoriented cycles (Q2048544): Difference between revisions

Summary: 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 a duality pair. In this work, for every undirected cycle \(C\) we find an orientation \(C_D\) and an oriented path \(P_C\), such that \((P_C,C_D)\) is a duality pair. As a consequence we obtain that there is a finite set, \(F_C\), such that an undirected graph is homomorphic to \(C\), if and only if it admits an \(F_C\)-free orientation. As a byproduct of the proposed duality pairs, we show that if \(T\) is an oriented tree of height at most \(3\), one can choose a dual of \(T\) of linear size with respect to the size of \(T\).