## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, May 16, 2019, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Erik Jahn

## 2-factors with k cycles in Hamiltonian graphs

A theorem by Brandt, Chen, Gould, Faudree and Lesniak states that if a graph G on n > 4k vertices has minimum degree at least n/2 then G contains a 2-factor consisting of exactly k cycles. This is quickly seen to be tight in terms of the bound on the minimum degree. However, if one assumes in addition that G is Hamiltonian it has been conjectured that the bound on the minimum degree may be relaxed. This was indeed shown to be true by Sarközy and after a series of improvements the best known result, due to DeBiasio, Ferrara and Morris, established that a minimum degree of (2/5 + o(1))n suffices. We present a major improvement of this result showing that the required minimum degree for large Hamiltonian graphs to have a 2-factor consisting of a fixed number of cycles is sublinear in n. This is joint work with M. Bucic, A. Pokrovskiy and B. Sudakov.

Information for students and suggested topics for student talks