Tournament pathwidth and topological containment

Alexandra Fradkin, Paul Seymour

Research output: Contribution to journalArticle

11 Scopus citations

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 languageEnglish (US)
Pages (from-to)374-384
Number of pages11
JournalJournal of Combinatorial Theory. Series B
Volume103
Issue number3
DOIs
StatePublished - 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