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.
Original language | English (US) |
---|---|
Pages (from-to) | 374-384 |
Number of pages | 11 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 103 |
Issue number | 3 |
DOIs | |
State | Published - May 2013 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
Keywords
- Bundles
- Jungles
- Pathwidth
- Topological containment
- Tournaments
- Vertex-disjoint paths