The oriented rainbow tree conjecture

Let DD be a digraph in which every vertex has dd incoming and dd outgoing edges, with no loops or parallel edges; both a→ba\to b and b→ab\to a may occur. It is properly coloured when the incoming edges at each vertex have distinct colours and the outgoing edges at each vertex have distinct colours. Let TT be an oriented tree with d−1d-1 edges; a copy is rainbow when its edges have distinct colours.

Oriented rainbow tree conjecture. Every dd-regular properly coloured digraph DD contains a rainbow copy of every oriented tree TT on d−1d-1 edges.

This strictly generalises the undirected regular-graph rainbow tree conjecture and implies several longstanding rainbow and rearrangement problems. The source explicitly describes the associated consequences as open.

References

Primary source

Alp Müyesser and Alexey Pokrovskiy, “On the Graham–Sloane harmonious labelling conjecture”, arXiv:2509.05280 (2025).

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.