Fractional clique decompositions of dense graphs. Issue 4 (18th October 2018)

• Record Type: Journal Article
• Authors: Montgomery, Richard
• Is Part Of: Random structures & algorithms. Volume 54:Issue 4(2019)
• Page Start: 779
• Page End: 796
• Publication Date: 2018-10-18
• Subjects: Graph decompositions -- Fractional graph theory -- clique decompositions; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20809
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: For each r ≥ 4, we show that any graph G with minimum degree at least ( 1 − 1 / ( 100 r ) ) | G | has a fractional K r ‐decomposition. This improves the best previous bounds on the minimum degree required to guarantee a fractional K r ‐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.