Duality pairs and homomorphisms to oriented and unoriented cycles

Abstract

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\nrightarrow H$. The directed path on $k+1$ vertices together with the transitive tournament on $k$ vertices is a classic example of a duality pair. This relation between paths and tournaments implies that a graph is $k$-colourable if and only if it admits an orientation with no directed path on more than $k$-vertices. 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 a tree of height at most $3$, one can choose a dual of $T$ of linear size with respect to the size of $T$.

13 pages, 4 figures