Cycle packing1. Issue 4 (16th October 2014)
- Record Type:
- Journal Article
- Title:
- Cycle packing1. Issue 4 (16th October 2014)
- Main Title:
- Cycle packing1
- Authors:
- Conlon, David
Fox, Jacob
Sudakov, Benny - 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>
- Is Part Of:
- Random structures & algorithms. Volume 45:Issue 4(2014)
- Journal:
- Random structures & algorithms
- Issue:
- Volume 45:Issue 4(2014)
- Issue Display:
- Volume 45, Issue 4 (2014)
- Year:
- 2014
- Volume:
- 45
- Issue:
- 4
- Issue Sort Value:
- 2014-0045-0004-0000
- Page Start:
- 608
- Page End:
- 626
- Publication Date:
- 2014-10-16
- Subjects:
- Random graphs -- Periodicals
Mathematical analysis -- Periodicals
519 - Journal URLs:
- http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1098-2418 ↗
http://onlinelibrary.wiley.com/ ↗ - DOI:
- 10.1002/rsa.20574 ↗
- Languages:
- English
- ISSNs:
- 1042-9832
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 7254.411950
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 4001.xml