The Library
Towards the Erdős-Gallai cycle decomposition conjecture
Tools
Tools
Tools
Bucić, Matija and Montgomery, Richard (2022) Towards the Erdős-Gallai cycle decomposition conjecture. (Submitted)
|
PDF
WRAP-Towards-the-Erdos-Gallai-cycle-decomposition-conjecture-Montgomery-2022.pdf - Submitted Version - Requires a PDF viewer. Download (730Kb) | Preview |
Abstract
In the 1960's, Erdős and Gallai conjectured that the edges of any n-vertex graph can be decomposed into O(n) cycles and edges. We improve upon the previous best bound of O(nloglogn) cycles and edges due to Conlon, Fox and Sudakov, by showing an n-vertex graph can always be decomposed into O(nlog∗n) cycles and edges, where log∗n is the iterated logarithm function.
| Item Type: | Submitted Journal Article | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||||
| Library of Congress Subject Headings (LCSH): | Computational complexity, Graph algorithms | ||||||||||||
| Official Date: | 14 November 2022 | ||||||||||||
| Dates: |
|
||||||||||||
| Number of Pages: | 26 | ||||||||||||
| Institution: | University of Warwick | ||||||||||||
| Status: | Not Peer Reviewed | ||||||||||||
| Publication Status: | Submitted | ||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
