Rooted grid minors

详细信息    查看全文

• 作者：Daniel Marx^a ; Paul Seymour^b ; ¹ ; ^{pds@math.princeton.edu} ; Paul Wollan^c ; ²
• 关键词：Grid minors ; Treewidth ; Tangles
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：428-437
• 全文大小：279 K
• 卷排序：122

文摘

Intuitively, a tangle of large order in a graph is a highly-connected part of the graph, and it is known that if a graph has a tangle of large order then it has a large grid minor. Here we show that for any k, if G has a tangle of large order and Z is a set of vertices of cardinality k that cannot be separated from the tangle by any separation of order less than k, then G has a large grid minor containing Z, in which the members of Z all belong to the outside of the grid.