论文标题
具有相同长度的所有引起的定向周期的挖掘图不是$ \ \vecχ$。
Digraphs with all induced directed cycles of the same length are not $\vecχ$-bounded
论文作者
论文摘要
对于$ t \ ge 2 $，如果所有诱导的定向周期$ d $的长度等于$ t $，则让我们称为Digraph $ d $ \ emph {t-chordal}。在上一篇论文中，我们询问了哪个$ t $的确是有界数的$ t $兄弟式图具有有限的二分法数。最近，Aboulker，Bousquet和de Verclos以$ t = 3 $的负面回答，也就是说，他们给出了$ 3 $的和差的挖掘机，其中包含$ 3 $的总数和任意较大的二分音数字。在本文中，我们扩展了它们的结果，给出了每个$ t \ ge 3 $ a的构造，其中包数为$ 3 $和任意大的二分法数，从而以负面的方式回答了我们的问题。另一方面，我们表明，一个更受限制的类，没有诱导的定向周期小于$ t $的digraphs，并且没有引起的定向$ t $ vertex路径，如果其集团数字有限，则具有界限二十五章。我们还显示了以下复杂性结果：对于固定的$ t \ ge 2 $，确定digraph是$ t $ - 句号的问题。
For $t \ge 2$, let us call a digraph $D$ \emph{t-chordal} if all induced directed cycles in $D$ have length equal to $t$. In a previous paper, we asked for which $t$ it is true that $t$-chordal graphs with bounded clique number have bounded dichromatic number. Recently, Aboulker, Bousquet, and de Verclos answered this in the negative for $t=3$, that is, they gave a construction of $3$-chordal digraphs with clique number at most $3$ and arbitrarily large dichromatic number. In this paper, we extend their result, giving for each $t \ge 3$ a construction of digraphs with clique number at most $3$ and arbitrarily large dichromatic number, thus answering our question in the negative. On the other hand, we show that a more restricted class, digraphs with no induced directed cycle of length less than $t$, and no induced directed $t$-vertex path, have bounded dichromatic number if their clique number is bounded. We also show the following complexity result: for fixed $t \ge 2$, the problem of determining whether a digraph is $t$-chordal is coNP-complete.
