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


Tree decompositions of graphs without large bipartite holes
Authors:Jaehoon Kim  Younjin Kim  Hong Liu
Abstract:A recent result of Condon, Kim, Kühn, and Osthus implies that for any urn:x-wiley:rsa:media:rsa20913:rsa20913-math-0001, an n‐vertex almost r‐regular graph G has an approximate decomposition into any collections of n‐vertex bounded degree trees. In this paper, we prove that a similar result holds for an almost αn‐regular graph G with any α>0 and a collection of bounded degree trees on at most (1?o(1))n vertices if G does not contain large bipartite holes. This result is sharp in the sense that it is necessary to exclude large bipartite holes and we cannot hope for an approximate decomposition into n‐vertex trees. Moreover, this implies that for any α>0 and an n‐vertex almost αn‐regular graph G, with high probability, the randomly perturbed graph urn:x-wiley:rsa:media:rsa20913:rsa20913-math-0002 has an approximate decomposition into all collections of bounded degree trees of size at most (1?o(1))n simultaneously. This is the first result considering an approximate decomposition problem in the context of Ramsey‐Turán theory and the randomly perturbed graph model.
Keywords:Tree decomposition  bipartite hole  Ramsey‐Turá  n  randomly perturbed graph model
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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