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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Topological containment
- Vertex-disjoint paths