Abstract
A fundamental theorem of Wilson states that, for every graph F, every sufficiently large F-divisible clique has an F-decomposition. Here a graph G is F -divisible if e(F) divides e(G) and the greatest common divisor of the degrees of F divides the greatest common divisor of the degrees of G, and G has an F-decomposition if the edges of G can be covered by edge-disjoint copies of F. We extend this result to graphs G which are allowed to be far from complete. In particular, together with a result of Dross, our results imply that every sufficiently large K3-divisible graph of minimum degree at least 9n/10+o(n) has a K3-decomposition. This significantly improves previous results towards the long-standing conjecture of Nash-Williams that every sufficiently large K3-divisible graph with minimum degree at least 3n/4 has a K3-decomposition. We also obtain the asymptotically correct minimum degree thresholds of 2n/3+o(n) for the existence of a C4-decomposition, and of n/2+o(n) for the existence of a C2ℓ-decomposition, where ℓ≥3. Our main contribution is a general ‘iterative absorption’ method which turns an approximate or fractional decomposition into an exact one. In particular, our results imply that in order to prove an asymptotic version of Nash-Williams' conjecture, it suffices to show that every K3-divisible graph with minimum degree at least 3n/4+o(n) has an approximate K3-decomposition.
Original language | English |
---|---|
Pages (from-to) | 337-385 |
Number of pages | 49 |
Journal | Advances in Mathematics |
Volume | 288 |
Early online date | 11 Nov 2015 |
DOIs | |
Publication status | Published - 22 Jan 2016 |
Keywords
- Extremal graph theory
- Probabilistic methods
- Edge-decompositions of graphs