首页 | 本学科首页   官方微博 | 高级检索  
     


Fractional clique decompositions of dense graphs
Authors:Richard Montgomery
Abstract:For each urn:x-wiley:10429832:media:rsa20809:rsa20809-math-0001, we show that any graph G with minimum degree at least urn:x-wiley:10429832:media:rsa20809:rsa20809-math-0002 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 urn:x-wiley:10429832:media:rsa20809:rsa20809-math-0003, and any urn:x-wiley:10429832:media:rsa20809:rsa20809-math-0004, any sufficiently large graph G with minimum degree at least urn:x-wiley:10429832:media:rsa20809:rsa20809-math-0005 has, subject to some further simple necessary divisibility conditions, an (exact) F‐decomposition.
Keywords:Graph decompositions  Fractional graph theory  clique decompositions
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号