Balanced tree decomposition conjecture for complete bipartite graphs

A balanced tree Tn,nT_{n,n} has nn vertices in each partition class, hence 2n2n vertices in total. A graph decomposes GG if copies of the graph form a perfect packing of GG.

Balanced tree decomposition conjecture. Any tree Tn,nT_{n,n} decomposes K2n1,2n1K_{2n-1,2n-1}.

This is presented as following from the Graham–Häggkvist conjecture for nn-regular bipartite graphs. The source then asks whether a smaller, possibly asymmetric host could suffice; the displayed decomposition assertion itself remains open.

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

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.

Solutions 0

No solutions have been posted yet.