Tree decompositions of graphs without large bipartite holes. Issue 1 (10th March 2020)

• Record Type: Journal Article
• Authors: Kim, Jaehoon; Kim, Younjin; Liu, Hong
• Is Part Of: Random structures & algorithms. Volume 57:Issue 1(2020)
• Page Start: 150
• Page End: 168
• Publication Date: 2020-03-10
• Subjects: Tree decomposition -- bipartite hole -- Ramsey‐Turán -- randomly perturbed graph model; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20913
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : A recent result of Condon, Kim, Kühn, and Osthus implies that for any r ≥ ( 1 2 + o ( 1 ) ) n, 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 G ∪ G ( n, O ( 1 n ) ) 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.