Premium
Fractional clique decompositions of dense graphs
Author(s) -
Montgomery Richard
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20809
Subject(s) - mathematics , combinatorics , degree (music) , clique , graph , divisibility rule , discrete mathematics , upper and lower bounds , physics , acoustics , mathematical analysis
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.