论文标题
Gyarfas-Sumner的猜想扩展到Digraphs
Extension of Gyarfas-Sumner conjecture to digraphs
论文作者
论文摘要
Digraph $ d $的二分法数量是为其顶点着色所需的最小颜色数量，每种颜色类都诱导一个无环的挖掘物。随着它概括了图形数量的概念，它一直是一个最近的研究中心。在这项工作中，我们研究了Gyárfás-Sumner猜想的可能扩展。更确切地说，我们建议作为猜想的有限套件的简单表征$ \ MATHCAL f $的DIGRAPHS，以便每个带有足够大的二分法数字的面向图形都必须包含$ \ Mathcal F $的成员，作为诱导子图。 在值得注意的结果中，我们证明没有定向长度$ 3 $的无定向路径的面向三角形的图形为$ 2 $ - 可油。如果“无三角形”的条件被“ $ k_4 $ - free”替换，那么我们的上限为$ 414 $。我们还表明，没有定向三角形的完整多部分图的方向是2色。为了证明这些结果，我们介绍了可能引起独立感兴趣的\ emph {nice sets}的概念。
The dichromatic number of a digraph $D$ is the minimum number of colors needed to color its vertices in such a way that each color class induces an acyclic digraph. As it generalizes the notion of the chromatic number of graphs, it has been a recent center of study. In this work we look at possible extensions of Gyárfás-Sumner conjecture. More precisely, we propose as a conjecture a simple characterization of finite sets $\mathcal F$ of digraphs such that every oriented graph with sufficiently large dichromatic number must contain a member of $\mathcal F$ as an induce subdigraph. Among notable results, we prove that oriented triangle-free graphs without a directed path of length $3$ are $2$-colorable. If condition of "triangle-free" is replaced with "$K_4$-free", then we have an upper bound of $414$. We also show that an orientation of complete multipartite graph with no directed triangle is 2-colorable. To prove these results we introduce the notion of \emph{nice sets} that might be of independent interest.
