# Edge-decompositions of graphs with high minimum degree

Research output: Contribution to journal › Article

## Authors

## Colleges, School and Institutes

## 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 K_{3}-divisible graph of minimum degree at least 0.956n has a K_{3}-decomposition. Our result significantly improves previous results towards the long-standing conjecture of Nash-Williams that every sufficiently large K_{3}-divisible graph with minimum degree 3n/4 has a K_{3}-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 C_{4} 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.

## Details

Original language | English |
---|---|

Pages (from-to) | 115-121 |

Number of pages | 7 |

Journal | Electronic Notes in Discrete Mathematics |

Volume | 49 |

Publication status | Published - 1 Nov 2015 |

## Keywords

- Edge decomposition, Minimum degree