论文标题
二元性对和同态与面向和非导向的周期
Duality pairs and homomorphisms to oriented and unoriented cycles
论文作者
论文摘要
在Digraphs的同态顺序中，二元性对是一对订购的Digraphs $（G，H）$，因此对于任何Digraph，$ d $，$ g \ to d $ i时，仅当$ d \ d \ to to H $时。 $ k+1 $顶点的指向路径以及$ k $顶点上的及时锦标赛是双重对的经典示例。路径和锦标赛之间的这种关系意味着，只有当它接收到$ k $颜色的$ k $彩色时，它才能在超过$ k $ vertices上没有定向路径的方向。 在这项工作中，对于每个无向周期$ c $，我们都会找到一个方向$ c_d $和定向路径$ p_c $，因此$（p_c，c_d）$是双重性对。结果，我们得到有限集，即$ f_c $，因此，当且仅当它承认$ f_c $ - free方向时，无方向的图是同型至$ c $的。作为拟议二元性对的副产品，我们表明，如果$ t $是最多3美元的高度树，则可以选择相对于$ t $的$ t $ t $线性大小的双t $。
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. 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$.
