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

*(English)*Zbl 1389.05058For 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\).

Reviewer: Wai-Kai Chen (Fremont)

##### MSC:

05C20 | Directed graphs (digraphs), tournaments |

05C35 | Extremal problems in graph theory |

05C40 | Connectivity |

PDF
BibTeX
XML
Cite

\textit{D. Kühn} et al., Combinatorica 36, No. 4, 451--469 (2016; Zbl 1389.05058)

Full Text:
DOI

##### References:

[1] | S. Abbasi: The solution of the El-Zahar Problem, Ph.D. Thesis, Rutgers University 1998. |

[2] | P. Camion: Chemins et circuits hamiltoniens des graphes complets, C. R. Acad. Sci.Paris 249 (1959), 2151–2152. · Zbl 0092.15801 |

[3] | G. Chen, R.J. Gould and H. Li: Partitioning vertices of a tournament into independentcycles, J. Combin. Theory B 83 (2001), 213–220. · Zbl 1028.05038 · doi:10.1006/jctb.2001.2048 |

[4] | P. Hajnal: Partition of graphs with condition on the connectivity and minimumdegree, Combinatorica 3 (1983), 95–99. · Zbl 0529.05030 · doi:10.1007/BF02579344 |

[5] | P. Keevash and B. Sudakov: Triangle packings and 1-factors in oriented graphs, J. Combin. Theory B 99 (2009), 709–727. · Zbl 1208.05038 · doi:10.1016/j.jctb.2008.12.004 |

[6] | D. KÜuhn, J. Lapinskas, D. Osthus and V. Patel: Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments, Proc. London Math Soc. 109 (2014), 733–762. · Zbl 1302.05069 · doi:10.1112/plms/pdu019 |

[7] | K. B. Reid: Two complementary circuits in two-connected tournaments, in: Cycles in Graphs, B.R. Alspach, C.D. Godsil, Eds., Ann. Discrete Math. 27 (1985), 321–334. · doi:10.1016/S0304-0208(08)73025-1 |

[8] | K. B. Reid: Three problems on tournaments, Graph Theory and its applications:East and West, Ann. New York Acad. Sci. 576 (1989), 466–473. |

[9] | Z. M. Song: Complementary cycles of all lengths in tournaments, J. Combin. Theory B 57 (1993), 18–25. · Zbl 0723.05062 · doi:10.1006/jctb.1993.1002 |

[10] | C. Thomassen: Graph decomposition with constraints on the connectivity and minimumdegree, J. Graph Theory 7 (1983), 165–167. · Zbl 0515.05045 · doi:10.1002/jgt.3190070204 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.