PROOF OF A TOURNAMENT PARTITION CONJECTURE AND AN APPLICATION TO 1-FACTORS WITH PRESCRIBED CYCLE LENGTHS

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 V1,..., Vt such that for all i the subtournament T [Vi] induced on T by Vi is strongly k-connected. Our main result implies an affirmative answer to this question. In particular we show that f(k, t) = O(k7t4) 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 an integer 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(t5) suffices. 1