### 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 1 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

## Fingerprint Dive into the research topics of 'Tournament pathwidth and topological containment'. Together they form a unique fingerprint.

## Cite this

Fradkin, A., & Seymour, P. (2013). Tournament pathwidth and topological containment.

*Journal of Combinatorial Theory. Series B*,*103*(3), 374-384. https://doi.org/10.1016/j.jctb.2013.03.001