论文标题
罗伯逊（Robertson）的猜想I.拓扑次要关系
Robertson's conjecture I. Well-quasi-ordering bounded tree-width graphs by the topological minor relation
论文作者
论文摘要
罗伯逊（Robertson）和西摩（Seymour）的著名图形定理指出，图形是由小小的关系序列的。与较小的关系不同，拓扑次要关系通常不是良好的级别图。在所有已知的无限抗相对于拓扑遏制方面，可以找到从任意长路径获得的图的细分，可以找到每个边缘。在1980年代，罗伯逊（Robertson）猜想这是唯一的障碍。正式地，他猜想，对于每个正整数$ k $，图表不包含从长度$ k $获得的图形来通过将每个边缘复制为拓扑的小小的图表的图表，这是由拓扑小调关系良好的序列。情况$ k = 1 $意味着克鲁斯卡尔的树定理，$ k = 2 $的情况意味着在亚立管图上的猜想。 这一系列论文献出了罗伯逊猜想的证明。在本文中，我们证明了罗伯逊（Robertson）对有限树宽度图的猜想。这是朝着罗伯逊猜想的完整证明的重要一步，本文中开发的机器将在该系列的未来论文中应用。本文证明了这个有界的树宽度案例，这意味着可以通过拓扑次要的关系来证明的所有已知结果，而无需使用图形次要定理，并且本文中我们的证明是独立的。
Robertson and Seymour's celebrated Graph Minor Theorem states that graphs are well-quasi-ordered by the minor relation. Unlike the minor relation, the topological minor relation does not well-quasi-order graphs in general. Among all known infinite antichains with respect to the topological containment, subdivisions of a graph obtained from an arbitrarily long path by duplicating each edge can be found. In the 1980's Robertson conjectured that this is the only obstruction. Formally, he conjectured that for every positive integer $k$, graphs that do not contain the graph obtained from a path of length $k$ by duplicating each edge as a topological minor are well-quasi-ordered by the topological minor relation. The case $k=1$ implies Kruskal's Tree Theorem, and the case $k=2$ implies a conjecture of Vázsonyi on subcubic graphs. This series of papers dedicates a proof of Robertson's conjecture. We prove Robertson's conjecture for graphs of bounded tree-width in this paper. It is an essential step toward the complete proof of Robertson's conjecture, and the machinery developed in this paper will be applied in future papers of the series. This bounded tree-width case proved in this paper implies all known results about well-quasi-ordering graphs by the topological minor relation that can be proved without using the Graph Minor Theorem, and our proof in this paper is self-contained.
