Towards the Erdős-Gallai cycle decomposition conjecture

Matija Bucić, Richard Montgomery

Research output: Contribution to journalArticlepeer-review

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(nlog⁡log⁡n) 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 languageEnglish (US)
Article number109434
JournalAdvances in Mathematics
Volume437
DOIs
StatePublished - Feb 2024

All Science Journal Classification (ASJC) codes

  • General Mathematics

Keywords

  • Erdős-Gallai conjecture
  • Expander decomposition
  • Graph decomposition
  • Sublinear expansion

Fingerprint

Dive into the research topics of 'Towards the Erdős-Gallai cycle decomposition conjecture'. Together they form a unique fingerprint.

Cite this