On 2-factors of k cycles

Graphs, Hypergraphs, and Computing

25 March 15:30 - 16:30

Ervin Gyori - Alfred Renyi Institute of Mathematics

Brandt, Chen, Faudree, Gould, Lesniak proved (in 1999!) for k>1 that if G is a graph of n vertices, n is large enough and all degrees are at least n/2 then G has a 2-factor of exactly k cycles. In this talk we cover related questions:

Egawa, Enomoto, Faudree, Li and Schiermeyer proved that the degree bound n/2 is sufficient for large enough n even if we have k prescribed vertices in these cycles. Then Egawa, Faudree, Gyori, Ishigami, Schelp and Wang determined sharp degree conditions if we we prescribe k independent edges in these k cycles.

If we have no restriction on the k cycles of the 2-factor then Faudree, Gould, Jacobson, Lesniak and Saito conjectured that the degree bound can be weakened if G has a Hamilton cycle. It was proved by Sarkozy that n/2 minus a tiny fraction of n is sufficient. Improvements of this theorem will be presented.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to