论文标题
在方向的完整多部分图中的英雄
Heroes in oriented complete multipartite graphs
论文作者
论文摘要
二分法数是其顶点的分区的最小尺寸，以无环诱导的子图。给定一类Digraphs $ \ MATHCAL C $，如果$ h $ h $ h $ free digraphs $ \ mathcal c $具有限制性二分法数，则digraph $ h $是$ \ mc c $的英雄。在一份开创性的论文中，伯杰在Al。简单地描述了锦标赛中所有英雄。在本文中，我们提供了一个简单的证据，证明了准传递的图表中的英雄与锦标赛中的英雄相同。我们还证明，在定向多部分图的类别中并非如此，反驳了Aboulker，Charbit和Naserasr的猜想。我们还将在定向的完整多部分图表中对英雄进行完整的描述，直至单一比赛的状态为6美元。
The dichromatic number of a digraph is the minimum size of a partition of its vertices into acyclic induced subgraphs. Given a class of digraphs $\mathcal C$, a digraph $H$ is a hero in $\mc C$ if $H$-free digraphs of $\mathcal C$ have bounded dichromatic number. In a seminal paper, Berger at al. give a simple characterization of all heroes in tournaments. In this paper, we give a simple proof that heroes in quasi-transitive oriented graphs are the same as heroes in tournaments. We also prove that it is not the case in the class of oriented multipartite graphs, disproving a conjecture of Aboulker, Charbit and Naserasr. We also give a full characterisation of heroes in oriented complete multipartite graphs up to the status of a single tournament on $6$ vertices.
