Erdős–Gallai linear cycle-and-edge decomposition conjecture
Erdős–Gallai linear cycle-and-edge decomposition conjecture
A decomposition of a graph is a partition of its edge set into subgraphs of the indicated types. Erdős–Gallai conjecture. Every -vertex graph has a decomposition into cycles and edges. The source says this is equivalent to the corresponding question for decomposing Eulerian graphs into cycles and records it as open.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Richard Montgomery, “Recent progress in graph theory using expansion”, arXiv:2607.26049 (2026).
Additional references
6 papers in this index state this conjecture (2013–2026). The statement above is taken from the most recent of them; the others are arXiv:2509.01901, arXiv:2401.10865, arXiv:2211.07689, arXiv:1911.05501, arXiv:1310.0632.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.