Packing large balanced trees into bipartite graphs

DOI10.1016/J.DISC.2025.114641MaRDI QIDQ6933600zbMATH OpenFDO

Authors Cristina G. Fernandes, Tássio Naia, Giovanne Santos, Maya Stein

Publication date 4 September 2025

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DISC.2025.114641

zbMATH Keywords

balanced treesgraph decompositiontree packing

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Review text

A family \(\mathcal{H}\) of graphs packs into a graph \(G\) if \(G\) contains pairwise edge-disjoint copies of all the members of \(\mathcal{H}\). The authors prove hat for every \(\gamma > 0 \) there exists \(n_0\in \mathbb{N}\) such that for every \( n\geq 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,n}\). They also show an approximate bipartite version of the Komlós-Sárközy-Szemerédi theorem.

Cites work

• A blow-up lemma for approximate decompositions
• A note on packing trees into complete bipartite graphs and on Fishburn's conjecture
• A proof of Ringel's conjecture
• Almost every tree with \(m\) edges decomposes \(K_{2m,2m}\)
• An approximate version of the Loebl-Komlós-Sós conjecture
• An approximate version of the tree packing conjecture
• Degree conditions for embedding trees
• Edge-decompositions ofK_n,ninto isomorphic copies of a given tree
• Embedding into Bipartite Graphs
• Finding large rainbow trees in colourings of \(K_{n, n}\)
• Generalizations of the tree packing conjecture
• scientific article; zbMATH DE number 4150219 (Why is no real title available?)
• scientific article; zbMATH DE number 4070955 (Why is no real title available?)
• scientific article; zbMATH DE number 3732107 (Why is no real title available?)
• scientific article; zbMATH DE number 3604921 (Why is no real title available?)
• scientific article; zbMATH DE number 3623611 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 861349 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• On packing trees into complete bipartite graphs
• On representatives of subsets.
• On the tree packing conjecture
• Packing almost stars into the complete graph
• Packing degenerate graphs
• Packing graphs with odd and even trees
• Packing minor-closed families of graphs into complete graphs
• Packing spanning graphs from separable families
• Packing three copies of a tree into a complete bipartite graph
• Packing trees in complete graphs
• Packing Trees into the Complete Graph
• Packing trees into \(n\)-chromatic graphs
• Packing trees into complete bipartite graphs
• Packing trees of bounded diameter into the complete graph
• Ringel's tree packing conjecture in quasirandom graphs
• Some remarks on packing trees
• Spanning trees in dense directed graphs
• Spanning trees in dense graphs

This page was built for publication: Packing large balanced trees into bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6933600)