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

DOI10.1007/S00493-015-3186-8MaRDI QIDQ1677541zbMATH OpenOpenAlexWikidataFDO

Authors Daniela Kühn, Deryk Osthus, Timothy Townsend

Publication date 10 November 2017

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.7677, http://pure-oai.bham.ac.uk/ws/files/25675966/TournamentConnectivity6.pdf

zbMATH Keywords

\(1\)-factor\(k\)-connected tournamenttournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Connectivity (05C40)

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 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(t^5) suffices.

Review text

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\).

Recommendations

• On 1-factors with prescribed lengths in tournaments
• Partitioning vertices of a tournament into independent cycles
• scientific article; zbMATH DE number 2192120

Cites work

• Complementary cycles of all lengths in tournaments
• Graph decomposition with constraints on the connectivity and minimum degree
• scientific article; zbMATH DE number 3150485 (Why is no real title available?)
• Partition of graphs with condition on the connectivity and minimum degree
• Partitioning vertices of a tournament into independent cycles
• Triangle packings and 1-factors in oriented graphs

Cited in

(15)

• The partition of a strong tournament
• Degree constrained 2-partitions of semicomplete digraphs
• Partitioning vertices of a tournament into independent cycles
• An improved linear connectivity bound for tournaments to be highly linked
• Spanning trees of dense directed graphs
• On 1-factors with prescribed lengths in tournaments
• Finding good 2-partitions of digraphs. II. Enumerable properties
• Finding good 2-partitions of digraphs. I. Hereditary properties
• Tournaments and Semicomplete Digraphs
• Elementary proof of a counting formula for acyclic bipartite tournaments
• Sparse highly connected spanning subgraphs in dense directed graphs
• Sparse spanning \(k\)-connected subgraphs in tournaments
• scientific article; zbMATH DE number 2192120 (Why is no real title available?)
• Disjoint Cycles in a Digraph with Partial Degree
• Complementary cycles of any length in regular bipartite tournaments

This page was built for publication: Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1677541)