On the decomposition threshold of a given graph

Stefan Glock, Daniela Kühn, Allan Lo, Richard Montgomery, Deryk Osthus

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)
129 Downloads (Pure)


We study the F-decomposition threshold δF for a given graph F. Here an F-decomposition of a graph G is a collection of edge-disjoint copies of F in G which togetherncover every edge of G. (Such an F-decomposition can only exist if G is F-divisible, i.e. if e(F) | e(G) and each vertex degree of G can be expressed as a linear combination of the vertex degrees of F.) The F-decomposition threshold δF is the smallest value ensuring that an F-divisible graph G on n vertices with δ(G) ≥ (δF + o(1))n has an F-decomposition. Our main results imply the following for a given graph F, where δ∗F is the fractional
version of δF and χ := χ(F): (i) δF ≤ max{δ∗F , 1 − 1/(χ + 1)}; (ii) if χ ≥ 5, then δF ∈ {δ∗F , 1 − 1/χ, 1 − 1/(χ + 1)}; (iii) we determine δF if F is bipartite. In particular, (i) implies that δKr = δ∗Kr. Our proof involves further developments of the recent ‘iterative’ absorbing approach.
Original languageEnglish
Pages (from-to)47-127
Number of pages81
JournalJournal of Combinatorial Theory. Series B
Early online date29 Mar 2019
Publication statusPublished - Nov 2019


  • Designs
  • Fractional graph decompositions
  • Graph decompositions
  • Minimum degree

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'On the decomposition threshold of a given graph'. Together they form a unique fingerprint.

Cite this