Balanced tree decomposition conjecture for complete bipartite graphs
Balanced tree decomposition conjecture for complete bipartite graphs
A balanced tree has vertices in each partition class, hence vertices in total. A graph decomposes if copies of the graph form a perfect packing of .
Balanced tree decomposition conjecture. Any tree decomposes .
This is presented as following from the Graham–Häggkvist conjecture for -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.