Premium
Cycle packing
Author(s) -
Conlon David,
Fox Jacob,
Sudakov Benny
Publication year - 2014
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20574
Subject(s) - combinatorics , conjecture , mathematics , enhanced data rates for gsm evolution , graph , upper and lower bounds , set (abstract data type) , random graph , discrete mathematics , computer science , mathematical analysis , telecommunications , programming language
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