The Graham–Häggkvist tree decomposition conjecture

About 10 years old · traced to

Let TT be a tree with nn edges, and let Kn,nK_{n,n} be the balanced complete bipartite graph with nn vertices in each part.

Graham–Häggkvist conjecture. The edge set of Kn,nK_{n,n} can be decomposed into copies of every nn-edge tree TT.

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

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.