Hobbs–Bourgeois–Kasiraj bipartite Tree Packing Conjecture

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 1

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).

Sources & referencesView supporting material

Primary source

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

1 week ago

Hobbs–Bourgeois–Kasiraj bipartite Tree Packing Conjecture

Equivalent formulations 1

Hobbs–Bourgeois–Kasiraj bipartite tree-packing conjecture

Primary source

Progress summary

Solutions 0