Open problems in Graph Decompositions

Every d-regular graph on an even number n of vertices with d ≥ 2⌈n/4⌉ − 1 decomposes into perfect matchings (is 1-factorizable).

Every graph with average degree greater than k − 1 contains every tree with k edges as a subgraph.

The edges of every connected graph on n vertices can be decomposed into at most ⌈n/2⌉ paths.

The edges of every graph with maximum degree Δ can be partitioned into at most ⌈(Δ + 1)/2⌉ linear forests (disjoint unions of paths).

A graph with maximum degree Δ > n/3 is class 2 (chromatic index Δ + 1) if and only if it contains an overfull subgraph — one with more edges than Δ·⌊|V|/2⌋.