Packing large balanced trees into bipartite graphs

Fernandes, CG; Naia, T; Santos G.; Stein M.

Keywords: Tree packing, Graph decomposition, Balanced trees

Abstract

We prove that for every ?>0 there exists n0?N such that for every n?n0 any family of up to [Formula presented] trees having at most (1??)n vertices in each bipartition class can be packed into Kn,n. As a tool for our proof, we show an approximate bipartite version of the Komlós–Sárközy–Szemerédi Theorem, which we believe to be of independent interest. © 2025 Elsevier B.V.

Más información

Título según WOS: Packing large balanced trees into bipartite graphs
Título según SCOPUS: Packing large balanced trees into bipartite graphs
Título de la Revista: Discrete Mathematics
Volumen: 348
Número: 12
Editorial: Elsevier B.V.
Fecha de publicación: 2025
Idioma: English
DOI:

10.1016/j.disc.2025.114641

Notas: ISI, SCOPUS