← All problems

Erdős Problem #184 — Cycle-and-edge decompositions of graphs

60 years old · traced to

For a finite graph G=(V,E)G=(V,E), write n=∣V∣n=|V|. A decomposition into cycles and edges means a partition of EE into edge sets of cycles and single-edge pieces; in particular, all pieces are pairwise edge-disjoint. The Erdős–Gallai question is whether there is an absolute constant CC such that, for every nn and every nn-vertex graph GG, such a decomposition has at most CnCn pieces. Equivalently, can the edges of every nn-vertex graph be partitioned into O(n)O(n) cycles and single edges, with the implied constant independent of both nn and GG? Bucić and Montgomery, Towards the Erdős-Gallai Cycle Decomposition Conjecture

Background

Erdős and Gallai proposed the conjecture in the 1960s. Allowing single edges is essential: a graph with odd-degree vertices cannot, in general, have all its edges partitioned into cycles. By contrast, Euler’s theorem implies that every graph whose vertex degrees are all even can be decomposed into cycles. The conjecture asks for a linear-size decomposition even when odd-degree vertices are present. Bucić and Montgomery, Towards the Erdős-Gallai Cycle Decomposition Conjecture

A simple greedy procedure repeatedly removes a longest cycle and leaves the edges that are not in any removed cycle as single-edge pieces; the resulting bound is O(nlog⁡n)O(n\log n). The first major improvement for general graphs reduced this to O(nlog⁡log⁡n)O(n\log\log n). These advances concern edge-disjoint decompositions, not merely covers in which cycles may share edges. A distinct, easier covering result allows overlaps: Pyber proved that any nn-vertex graph’s edges can be covered by n−1n-1 cycles and edges. Bucić and Montgomery, Towards the Erdős-Gallai Cycle Decomposition Conjecture

References

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.