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
Adam Mickiewicz University
Technical University of Denmark, DTU