Edge-decompositions of graphs with high minimum degree

Ben Barber, Daniela Kühn, Allan Lo, Deryk Osthus

Research output: Contribution to journalArticle (Academic Journal)peer-review

40 Citations (Scopus)
388 Downloads (Pure)

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 languageEnglish
Pages (from-to)337-385
Number of pages49
JournalAdvances in Mathematics
Volume288
Early online date11 Nov 2015
DOIs
Publication statusPublished - 22 Jan 2016

Keywords

  • Extremal graph theory
  • Probabilistic methods
  • Edge-decompositions of graphs

Fingerprint

Dive into the research topics of 'Edge-decompositions of graphs with high minimum degree'. Together they form a unique fingerprint.

Cite this