Tournament pathwidth and topological containment

被引：10

作者：

Fradkin, Alexandra ^{[1
]}

Seymour, Paul ^{[2
]}

机构：

[1] Ctr Commun Res, Princeton, NJ 08540 USA

[2] Princeton Univ, Princeton, NJ 08544 USA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2013年 / 103卷 / 03期

基金：

美国国家科学基金会;

关键词：

Tournaments; Pathwidth; Topological containment; Bundles; Jungles; Vertex-disjoint paths;

D O I：

10.1016/j.jctb.2013.03.001

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that if a tournament has pathwidth >= 4 theta(2) + 7 theta then it has theta vertices that are pairwise theta-connected. As a consequence of this and previous results, we obtain that for every set S of tournaments the following are equivalent: there exists k such that every member of S has pathwidth at most k, there is a digraph H such that no subdivision of H is a subdigraph of any member of S, there exists k such that for each T is an element of S, there do not exist k vertices of T that are pairwise k-connected. As a further consequence, we obtain a polynomial-time algorithm to test whether a tournament contains a subdivision of a fixed digraph H as a subdigraph. (C) 2013 Elsevier Inc. All rights reserved.

引用

页码：374 / 384

页数：11