The Graham–Häggkvist tree decomposition conjecture
Let be a tree with edges, and let be the balanced complete bipartite graph with vertices in each part.
Graham–Häggkvist conjecture. The edge set of can be decomposed into copies of every -edge tree .
This is the bipartite analogue of the tree-decomposition conjecture associated with Ringel. The source states that it remains open, although the paper discusses rainbow embedding approaches.
References
Primary source
Alp Müyesser and Alexey Pokrovskiy, “On the Graham–Sloane harmonious labelling conjecture”, arXiv:2509.05280 (2025).
Additional references
3 papers in this index state this conjecture (2016–2025). The statement above is taken from the most recent of them; the others are arXiv:2008.00926, arXiv:1607.01456.
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
No solutions have been posted yet.