Fractional clique decompositions of dense graphs
Fractional clique decompositions of dense graphs
复制标题
稠密图的分数派分解
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
R. Montgomery
中科院分区：
文献类型：
--
作者：
R. Montgomery
对于每个r≥4，我们证明了任一度至少为(1−1/(100r))|G|的图G有分数Kr-分解。这改进了Dukes(对于小r)和Barber，Kühn，Lo，Montgomery和Ospus(对于大r)所给出的保证分数Kr分解所需的最小度的最好先前界，给出了紧到r的常数倍数的第一个界(例如，通过考虑Turán图)。结合Glock，Kühn，Lo，Montgomery和Ospus的工作，证明了对于任何色数为χ(F)≥4的图F和任何ε>；0，任何足够大的最小度至少为(1−1/(100χ(F))+ε)的图G|G|有(精确)F-分解，且满足一些更简单的必要条件。
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.
DOI：
10.1016/j.jctb.2017.05.005
发表时间：
2017
期刊：
Journal of Combinatorial Theory, Series B
影响因子：
--
作者：
Barber B
通讯作者：
Barber B
DOI：
10.1016/j.jctb.2019.02.010
发表时间：
2019
期刊：
Journal of Combinatorial Theory, Series B
影响因子：
--
作者：
Glock S
通讯作者：
Glock S