Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657045 | Journal of Combinatorial Theory, Series B | 2013 | 11 Pages |
Abstract
We prove that if a tournament has pathwidth ⩾4θ2+7θ then it has θ vertices that are pairwise θ-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∈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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics