Graph minors. XXI. Graphs with unique linkages
Graph minors. XXI. Graphs with unique linkages
复制标题
图未成年人。
DOI：
10.1016/j.jctb.2008.08.003
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
P. Seymour
中科院分区：
文献类型：
--
作者：
N. Robertson;P. Seymour
图G中的连杆L是一个子图，它的每个分量都是一条路径，如果V(L)=V(G)，并且G中没有其他连接相同顶点对的连杆，这是至关重要的。我们证明，如果G与p个分量有一个重要的连杆，那么G的树宽度由p的一个函数所限。这是证明图小项XIII中未证明引理的主要步骤，并且它有许多其他的应用，包括缠结猜想的构造性证明。
A linkage L in a graph G is a subgraph each component of which is a path, and it is vital if V(L)=V(G) and there is no other linkage in G joining the same pairs of vertices. We show that, if G has a vital linkage with p components, then G has tree-width bounded above by a function of p. This is the major step in the proof of the unproved lemma from Graph Minors XIII, and it has a number of other applications, including a constructive proof of the intertwining conjecture.