Tournament pathwidth and topological containment

Abstract

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.