Cycle packing1. Issue 4 (6th February 2015)

• Record Type: Journal Article
• Authors: Conlon, David; Fox, Jacob; Sudakov, Benny
• Is Part Of: Random structures & algorithms. Volume 45:Issue 4(2014)
• Page Start: 608
• Page End: 626
• Publication Date: 2015-02-06
• Subjects: graph decompositions -- cycles -- expanders -- Erdős‐Gallai conjecture; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20574
• Languages: English
• ISSNs: 1042-9832

Abstract

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