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