论文标题
二分法数和强制分区
Dichromatic number and forced subdivisions
论文作者
论文摘要
我们调查了二分法数量的二分法数量的界限，这些图形避免了固定的Digraph作为拓扑辅助。对于Digraph $ f $，用$ \ text {mader} _ {\vecχ}（f）$表示最小的整数$ k $，这样每一个$ k $ -dichromatic digraph都包含$ f $的细分。作为我们的第一个主要结果，我们证明，如果$ f $是周期的方向，则$ \ text {mader} _ {\vecχ}（f）= v（f）$。这解决了Aboulker，Cohen，Havet，Lochet，Moura和Thomassé的猜想。我们还将这一结果扩展到仙人掌图的更一般的方向以及生物学森林。我们的第二个主要结果是$ \ text {mader} _ {\vecχ}（f）（f）= 4 $，每次订单$ f $ $ 4 $。这是Dirac对经典结果的扩展，即$ 4 $ -CHROMATIC图包含$ K_4 $ -Subdivision的定向图。
We investigate bounds on the dichromatic number of digraphs which avoid a fixed digraph as a topological minor. For a digraph $F$, denote by $\text{mader}_{\vecχ}(F)$ the smallest integer $k$ such that every $k$-dichromatic digraph contains a subdivision of $F$. As our first main result, we prove that if $F$ is an orientation of a cycle then $\text{mader}_{\vecχ}(F)=v(F)$. This settles a conjecture of Aboulker, Cohen, Havet, Lochet, Moura and Thomassé. We also extend this result to the more general class of orientations of cactus graphs, and to bioriented forests. Our second main result is that $\text{mader}_{\vecχ}(F)=4$ for every tournament $F$ of order $4$. This is an extension of the classical result by Dirac that $4$-chromatic graphs contain a $K_4$-subdivision to directed graphs.
