Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths

Daniela Kühn, Deryk Osthus, Timothy Townsend

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)
131 Downloads (Pure)

Abstract

In 1982 Thomassen asked whether there exists an integer f(k,t) such that every strongly f(k,t)-connected tournament T admits a partition of its vertex set into t vertex classes V 1,…V t such that for all i the subtournament T[V i] induced on T by V i is strongly k-connected. Our main result implies an affirmative answer to this question. In particular we show that f(k, t)=O(k 7 t 4) suffices. As another application of our main result we give an affirmative answer to a question of Song as to whether, for any integer t, there exists aninteger h(t) such that every strongly h(t)-connected tournament has a 1-factor consisting of t vertex-disjoint cycles of prescribed lengths. We show that h(t)=O(t 5) suffices.

Original languageEnglish
Pages (from-to)451-469
Number of pages19
JournalCombinatorica
Volume36
Issue number4
Early online date24 Jun 2015
DOIs
Publication statusPublished - Aug 2016

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths'. Together they form a unique fingerprint.

Cite this