dc.contributor.author
Fernandes, Cristina G.
dc.contributor.author
Naia, Tássio
dc.contributor.author
Santos, Giovanne
dc.contributor.author
Stein, Maya
dc.date.accessioned
2026-03-05T14:03:03Z
dc.date.available
2026-03-05T14:03:03Z
dc.date.issued
2025-12-01
dc.identifier.uri
https://hdl.handle.net/2072/489275
dc.description.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.
ca
dc.description.sponsorship
✩ This research was initiated at the first “ChiPaGra: Workshop Chileno Paulista em/en Grafos”, and was partially supported by the research project 2019/13364-7: “Extremal and Structural Problems in Graph Theory”, funded by FAPESP (The São Paulo Research Foundation) and ANID (Agencia Nacional de Investigación y Desarrollo). * Corresponding author. E-mail addresses: cris@ime.usp.br (C. G. Fernandes), tnaia@member.fsf.org (T. Naia), gsantos@dim.uchile.cl (G. Santos), mstein@dim.uchile.cl (M. Stein). 1 CGF acknowledges partial support by CNPq (Proc. 423833/2018-9 and 310979/2020-0). 2 TN was supported by the Grant PID2020-113082GB-I00 funded by MICIU/AEI/ 10.13039/501100011033. This work is supported by the Spanish State Research Agency, through the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M). 3 GS was supported by ANID Doctorado Nacional 21221049. 4 MS is also affiliated to Centro de M
ca
dc.relation.ispartof
Discrete Mathematics
ca
dc.rights
Attribution 4.0 International
*
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
*
dc.source
RECERCAT (Dipòsit de la Recerca de Catalunya)
dc.subject.other
Tree packing
ca
dc.subject.other
Graph decomposition
ca
dc.subject.other
Balanced trees
ca
dc.title
Packing large balanced trees into bipartite graphs
ca
dc.type
info:eu-repo/semantics/article
ca
dc.description.version
info:eu-repo/semantics/publishedVersion
ca
dc.identifier.doi
10.1016/j.disc.2025.114641
ca
dc.rights.accessLevel
info:eu-repo/semantics/openAccess
