Problem dossier · Graph Decompositions
1-Factorization conjecture
Every d-regular graph on an even number n of vertices with d ≥ 2⌈n/4⌉ − 1 decomposes into perfect matchings (is 1-factorizable).
§1
Status
Proved for all sufficiently large n (Csaba–Kühn–Lo–Osthus–Treglown, 2016); small cases remain unconsolidated.
Think you can crack this one? Read the playbook before you announce →
§2
The Angle of Attack
Test edge-coloring algorithms on small dense regular graphs at the threshold; search for the extremal graphs that make the bound tight.
Tags: matchings · edge coloring · regular graphs
§3
The Lab
No instruments built yet. When this problem gets tackled, its interactive instruments — explorers, searches, verifiers running in the browser — live here. See the Collatz dossier for what a fully tackled problem looks like.
§4
The Log
Empty. Work on this problem gets logged here as dated entries — constructions tried, code run, dead ends included. Dead ends are results.
§5
Related Problems
More open problems in Graph Decompositions and adjacent territory.
- Erdős–Sós conjecture — Graph Decompositions
- Gallai's path decomposition conjecture — Graph Decompositions
- Linear arboricity conjecture — Graph Decompositions
- Overfull conjecture — Graph Decompositions