2020/03/12 by Guzmán-Pro, Santiago, Hernández-Cruz, César
#05C60 #05C75 #68R10 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2003.05605
In the homomorphism order of digraphs, a duality pair is an ordered pair of digraphs (G,H) such that for any digraph, D, G→ D if and only if D\not→ 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 CD and an oriented path PC, such that (PC,CD) is a duality pair. As a consequence we obtain that there is a finite set, FC, such that an undirected graph is homomorphic to C, if and only if it admits an FC-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.