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 which are allowed to be far from complete: our results imply that every sufficiently large F-divisible graph G on n vertices with minimum degree at least (1-1/(16|F|4)+ε)n has an F-decomposition. Moreover, every sufficiently large K3-divisible graph of minimum degree at least 0.956n has a K3-decomposition. Our result significantly improves previous results towards the long-standing conjecture of Nash-Williams that every sufficiently large K3-divisible graph with minimum degree 3n/4 has a K3-decomposition. For certain graphs, we can strengthen the general bound above. In particular, we obtain the asymptotically correct thresholds of 2n/3+o(n) for C4 and n/2+o(n) for even cycles of length at least 6. Our main contribution is a general method which turns an approximate decomposition into an exact one.
Original language | English |
---|---|
Pages (from-to) | 115-121 |
Number of pages | 7 |
Journal | Electronic Notes in Discrete Mathematics |
Volume | 49 |
DOIs | |
Publication status | Published - 1 Nov 2015 |
Keywords
- Edge decomposition
- Minimum degree
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics