Journal
ADVANCES IN MATHEMATICS
Volume 437, Issue -, Pages -Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.aim.2023.109434
Keywords
Sublinear expansion; Expander decomposition; Graph decomposition; Erdos-Gallai conjecture
Categories
Ask authors/readers for more resources
This article improves upon previous research by showing that any n-vertex graph can be decomposed into O(n log* n) cycles and edges.
In the 1960's, Erdos 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(n log log n) cycles and edges due to Conlon, Fox and Sudakov, by showing an n-vertex graph can always be decomposed into O(n log* n) cycles and edges, where log* n is the iterated logarithm function.(c) 2023 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
