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.
Original language | English (US) |
---|---|
Article number | 109434 |
Journal | Advances in Mathematics |
Volume | 437 |
DOIs | |
State | Published - Feb 2024 |
All Science Journal Classification (ASJC) codes
- General Mathematics
Keywords
- Erdős-Gallai conjecture
- Expander decomposition
- Graph decomposition
- Sublinear expansion