The oriented rainbow tree conjecture

From papers

Let DD be a digraph in which every vertex has dd incoming and dd outgoing edges, with no loops or parallel edges; both aba\to b and bab\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 d1d-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 d1d-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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.