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

For any integer \(k\), a tournament \(T\) is said to be strongly \(k\)-connected if the number of vertices of \(T\) is greater than \(k\) and the removal of any set of fewer than \(k\) vertices results in a strongly connected tournament. The main purpose of the present paper is to show that there exists an integer \(f\) such that every strongly \(f\)-connected tournament \(T\) admits a partition of its vertex set into \(j\) vertex classes \(V_1, V_2,\ldots ,V_j\) such that, for all \(i\), the subtournament induced on the tournament \(T\) by the vertex set \(V_i\) is strongly \(k\)-connected. In addition, it is shown that for any integer \(j\), there exists an integer \(h\) such that every strongly \(h\)-connected tournament has a \(1\)-factor consisting of \(j\) vertex-disjoint cycles of prescribed lengths. The paper also gives an estimate on the maximum number of operations required in computing the integers \(f\) and \(h\).