论文标题
良好的序列挖掘没有牢固的浸入关系，没有很长的交替路径
Well-quasi-ordering digraphs with no long alternating paths by the strong immersion relation
论文作者
论文摘要
纳什·威廉姆斯（Nash-Williams）的强烈沉浸式猜想指出，图形是通过牢固的浸入关系序列的。也就是说，给定许多图，一个图包含另一个图作为强烈的沉浸。在本文中，我们研究了有向图的类似问题。众所周知，挖掘者不是通过牢固的浸入关系来良好的序列，但是对于所有已知的无限敌壁，可以找到任意多次改变方向的路径。本文证明了相反的说明是正确的：对于每个积极的整数$ k $，即使在牢固的沉浸关系中，不包含改变方向$ k $ times的道路的挖掘物，即使顶点被良好的序列标记。该结果对于在采用子图下关闭的分类类别是最佳的，因为相对于牢固的沉浸关系，用顶点标签任意多次改变方向的路径形成了无限的抗小节。
Nash-Williams' Strong Immersion Conjecture states that graphs are well-quasi-ordered by the strong immersion relation. That is, given infinitely many graphs, one graph contains another graph as a strong immersion. In this paper we study the analogous problem for directed graphs. It is known that digraphs are not well-quasi-ordered by the strong immersion relation, but for all known such infinite antichains, paths that change direction arbitrarily many times can be found. This paper proves that the converse statement is true: for every positive integer $k$, the digraphs that do not contain a path that changes direction $k$ times are well-quasi-ordered by the strong immersion relation, even when vertices are labelled by a well-quasi-order. This result is optimal for classes of digraphs closed under taking subgraphs since paths that change direction arbitrarily many times with vertex-labels form an infinite antichain with respect to the strong immersion relation.
