Graham–Häggkvist conjecture for complete bipartite hosts

About 2 years old · traced to

A graph decomposes GG if copies of the graph form a perfect packing of GG, and Kn,nK_{n,n} denotes the complete bipartite graph with nn vertices in each part.

Graham–Häggkvist complete-bipartite conjecture. Any tree of order n+1n+1 decomposes the complete bipartite graph Kn,nK_{n,n}.

This follows from the stated conjecture that every tree of order n+1n+1 decomposes every nn-regular bipartite graph. The source reports approximate results and evidence, but the exact assertion remains open.

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

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.