Duality pairs and homomorphisms to oriented and unoriented cycles (Q2048544): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 20:46, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Duality pairs and homomorphisms to oriented and unoriented cycles |
scientific article |
Statements
Duality pairs and homomorphisms to oriented and unoriented cycles (English)
0 references
6 August 2021
0 references
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\).
0 references
oriented path
0 references
undirected cycle
0 references