Fractional clique decompositions of dense graphs

Richard Montgomery

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
174 Downloads (Pure)

Abstract

For each r ≥ 4, we show that any graph G with minimum degree at least (1 − 1/(100r))|G| has a fractional Kr-decomposition. This improves the best previous bounds on the minimum degree required to guarantee a fractional Kr-decomposition given by Dukes (for small r) and Barber, Kühn, Lo, Montgomery and Osthus (for large r), giving the first bound that is tight up to the constant multiple of r (seen, for example, by considering Turán graphs). In combination with work by Glock, Kühn, Lo, Montgomery and Osthus, this shows that, for any graph F with chromatic number χ(F) ≥ 4, and any ε > 0, any sufficiently large graph G with minimum degree at least (1 − 1/(100χ(F)) + ε)|G| has, subject to some further simple necessary divisibility conditions, an (exact) F-decomposition.
Original languageEnglish
Pages (from-to)779-796
Number of pages18
JournalRandom Structures and Algorithms
Volume54
Issue number4
Early online date18 Oct 2018
DOIs
Publication statusPublished - Jul 2019

Keywords

  • Graph decomposition
  • Fractional graph theory
  • clique decompositions

Fingerprint

Dive into the research topics of 'Fractional clique decompositions of dense graphs'. Together they form a unique fingerprint.

Cite this