高色数和高最小出度有向图中圈的方向
Orientations of cycles in digraphs of high chromatic number and high minimum out-degree
摘要 Abstract
我们刻画了所有满足如下条件的圈的方向 $C$:对于任意固定的 $\varepsilon > 0$,存在常数 $c \geq 1$,使得每个不含环和平行弧的有向图 $D$,若其色数 $\chi(D) \geq c$ 且最小出度至少为 $\varepsilon |V(D)|$,则 $D$ 中包含 $C$ 作为子图。这一结果推广了Thomassen的结果。
We characterize all orientations of cycles $C$ for which for every fixed $\varepsilon > 0$ there exists a constant $c \geq 1$ such that every digraph $D$ without loops or parallel arcs with $\chi(D) \geq c$ and minimum out-degree at least $\varepsilon |V(D)|$ contains $C$ as a subdigraph. This generalizes a result of Thomassen.