论文标题
方向在三个顶点上没有禁止模式
Orientations without forbidden patterns on three vertices
论文作者
论文摘要
鉴于$ f $的定向图，如果$ f $ graph允许$ f $ g $，则是$ f $ f $ fule -f $ f $ fr的方向。在Bang-Jensen和Urrutia的先前工作的基础上，我们提出了一种主算法，该算法确定图表是否可以接纳$ f $ f $ - f $ f $是$ f $是$ p_3 $的方向的一个子集，而及时的三角则是。 我们通过研究$ f $ graphs的班级来扩展Skrien的先前结果，当$ f $是第三订单的任何定向图表时。除了所谓的完全取向图形和其子类之一外，还提供了所有此类集合的结构特征，这些图作为空旷的问题。
Given a set $F$ of oriented graphs, a graph $G$ is an $F$-graph if it admits an $F$-free orientation. Building on previous work by Bang-Jensen and Urrutia, we propose a master algorithm that determines if a graph admits an $F$-free orientation when $F$ is a subset of the orientations of $P_3$ and the transitive triangle. We extend previous results of Skrien by studying the class of $F$-graphs, when $F$ is any set of oriented graphs of order three. Structural characterizations for all such sets are provided, except for the so-called perfectly-orientable graphs and one of its subclasses, which remain as open problems.
