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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom