Cycle packing1. Issue 4 (6th February 2015) - Conlon, David; Fox, Jacob; Sudakov, Benny
Abstract: In the 1960s, Erdős and Gallai conjectured that the edge set of every graph on n vertices can be partitioned into O ( n ) cycles and edges. They observed that one can easily get an O ( nlogn ) upper bound by repeatedly removing the edges of the longest cycle. We make the first progress on this problem, showing that O ( nloglogn ) cycles and edges suffice. We also prove the Erdős‐Gallai conjecture for random graphs and for graphs with linear minimum degree. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 608–626, 2014