Cycle packing1. Issue 4 (16th October 2014)

• 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: 2014-10-16
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20574
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>In the 1960s, Erdős and Gallai conjectured that the edge set of every graph on <italic>n</italic> vertices can be partitioned into <italic>O</italic>(<italic>n</italic>) cycles and edges. They observed that one can easily get an <italic>O</italic>(<italic>nlogn</italic>) upper bound by repeatedly removing the edges of the longest cycle. We make the first progress on this problem, showing that <italic>O</italic>(<italic>nloglogn</italic>) 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</p> </abstract>