Hobbs–Bourgeois–Kasiraj bipartite Tree Packing Conjecture

About 2 years old · traced to 2024

For each $i$ , let $T_i$ be an arbitrary tree of order $i$ . A family packs into $G$ if $G$ contains pairwise edge-disjoint copies of all its members, and $K_{\lceil n/2\rceil,n-1}$ is the complete bipartite graph with parts of the indicated sizes.

Hobbs–Bourgeois–Kasiraj conjecture. Any family of trees $T_1,\dots,T_n$ packs into $K_{\lceil n/2\rceil,n-1}$ .

This is a bipartite-host variant of Gyárfás's Tree Packing Conjecture. The source gives partial and approximate results, but the exact statement remains open.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

Hobbs–Bourgeois–Kasiraj bipartite tree-packing conjecture
Let $[n]=\{1,\ldots,n\}$ , and let $(T_j)_{j\in[n]}$ be a family of trees with $v(T_j)=j$ for every $j\in[n]$ . Hobbs–Bourgeois–Kasiraj conjecture. If $n$ is even, the family packs into $K_{n-1,n/2}$ ; if $n$ is odd, it packs into $K_{n,(n-1)/2}$ . This is a bipartite-host modification of Gyárfás's Tree Packing Conjecture, attributed in the source to Hobbs, Bourgeois, and Kasiraj. The supplied status evidence indicates an asymptotic solution for bounded-maximum-degree trees, but does not establish the full conjecture.
source: Julia Böttcher, Jan Hladký, Diana Piguet and Anusch Taraz, “An approximate version of the Tree Packing Conjecture”, arXiv:1404.0697 (2014).

References

Primary source

Cristina G. Fernandes, Tássio Naia, Giovanne Santos and Maya Stein, “Packing large balanced trees into bipartite graphs”, arXiv:2410.13290 (2024).

Posted 1 month ago

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

No solutions have been posted yet.

Hobbs–Bourgeois–Kasiraj bipartite tree-packing conjecture

Primary source

Progress summary