Towards the ErdÅ's-Gallai Cycle Decomposition Conjecture

Matija Bucić, Richard Montgomery

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


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(n loglogn) 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. Our arguments make use and further develop the theory of robust sublinear expander graphs.

Original languageEnglish (US)
Title of host publicationSTOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing
EditorsBarna Saha, Rocco A. Servedio
PublisherAssociation for Computing Machinery
Number of pages14
ISBN (Electronic)9781450399135
StatePublished - Jun 2 2023
Event55th Annual ACM Symposium on Theory of Computing, STOC 2023 - Orlando, United States
Duration: Jun 20 2023Jun 23 2023

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Conference55th Annual ACM Symposium on Theory of Computing, STOC 2023
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Software


  • Decomposition into expanders
  • Erdos-Gallai Conjecture
  • Graph decomposition
  • Robust sublinear expanders


Dive into the research topics of 'Towards the ErdÅ's-Gallai Cycle Decomposition Conjecture'. Together they form a unique fingerprint.

Cite this