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 language | English |
---|---|
Pages (from-to) | 779-796 |
Number of pages | 18 |
Journal | Random Structures and Algorithms |
Volume | 54 |
Issue number | 4 |
Early online date | 18 Oct 2018 |
DOIs | |
Publication status | Published - Jul 2019 |
Keywords
- Graph decomposition
- Fractional graph theory
- clique decompositions