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

About 13 years old · traced to

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.

References

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.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.