Packing large balanced trees into bipartite graphs

Abstract

We prove that for every gamma>0 there exists n(0)is an element of N such that for every n >= n(0) any family of up to n(1/2-gamma) trees having at most (1-gamma)n vertices in each bipartition class can be packed into K-n,K-n. As a tool for our proof, we show an approximate bipartite version of the Koml & oacute;s-S & aacute;rk & ouml;zy-Szemer & eacute;di Theorem, which we believe to be of independent interest. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.