Well-quasi-ordering digraphs with no long alternating paths by the strong immersion relation
Well-quasi-ordering digraphs with no long alternating paths by the strong immersion relation
复制标题
强浸没关系的良好准序有向图，没有长交替路径
DOI：
10.1016/j.jctb.2022.08.007
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Muzi, Irene
中科院分区：
文献类型：
--
作者：
Liu, Chun-Hung;Muzi, Irene
纳什-威廉姆斯的强浸入猜想指出，图是由强浸入关系良准排序的。也就是说，给定无限多个图，一个图包含另一个图作为强沉浸。在本文中，我们研究有向图的类似问题。众所周知，有向图并不是通过强浸入关系来准排序的，但是对于所有已知的这种无限反链，可以找到任意多次改变方向的路径。本文证明了相反的陈述是正确的：对于每个正整数k，不包含改变方向k次的路径的有向图通过强浸入关系是良好拟序的，即使顶点被良好拟序标记。这个结果对于在获取子图时封闭的有向图类别来说是最佳的，因为使用顶点标签任意多次改变方向的路径形成相对于强沉浸关系的无限反链。
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 integerk, the digraphs that do not contain a path that changes directionktimes are well-quasi-ordered by the strong immersion relation, even when vertices are labeled 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.