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$.
@article{10_37236_9747,
author = {Santiago Guzm\'an-Pro and C\'esar Hern\'andez-Cruz},
title = {Duality pairs and homomorphisms to oriented and unoriented cycles},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {3},
doi = {10.37236/9747},
zbl = {1470.05117},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9747/}
}
TY - JOUR
AU - Santiago Guzmán-Pro
AU - César Hernández-Cruz
TI - Duality pairs and homomorphisms to oriented and unoriented cycles
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/9747/
DO - 10.37236/9747
ID - 10_37236_9747
ER -
%0 Journal Article
%A Santiago Guzmán-Pro
%A César Hernández-Cruz
%T Duality pairs and homomorphisms to oriented and unoriented cycles
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/9747/
%R 10.37236/9747
%F 10_37236_9747
Santiago Guzmán-Pro; César Hernández-Cruz. Duality pairs and homomorphisms to oriented and unoriented cycles. The electronic journal of combinatorics, Tome 28 (2021) no. 3. doi: 10.37236/9747
