Erdős–Gallai linear cycle-and-edge decomposition conjecture

From papers

A decomposition of a graph is a partition of its edge set into subgraphs of the indicated types. Erdős–Gallai conjecture. Every nn-vertex graph has a decomposition into O(n)O(n) cycles and edges. The source says this is equivalent to the corresponding question for decomposing Eulerian graphs into O(n)O(n) 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

No solutions have been posted yet.