Problem dossier · Graph Decompositions
Linear arboricity conjecture
The edges of every graph with maximum degree Δ can be partitioned into at most ⌈(Δ + 1)/2⌉ linear forests (disjoint unions of paths).
§1
Status
Open. Known asymptotically (Δ/2 + O(Δ^{2/3−ε}) forests suffice, Ferber–Fox–Jain and successors); exact for many classes.
Think you can crack this one? Read the playbook before you announce →
§2
The Angle of Attack
Verify decompositions on small graphs at odd Δ where the bound is tight; implement and stress the probabilistic decomposition algorithms on structured families.
Tags: linear forests · decomposition · paths · arboricity
§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.
- 1-Factorization conjecture — Graph Decompositions
- Erdős–Sós conjecture — Graph Decompositions
- Gallai's path decomposition conjecture — Graph Decompositions
- Overfull conjecture — Graph Decompositions