Schrijver's rainbow path conjecture

Let GG be a dd-regular graph. A proper edge-coloring is an edge-coloring in which adjacent edges receive distinct colors, and a path is rainbow if all its edges have distinct colors.

Schrijver's conjecture. If GG is a properly edge-colored dd-regular graph, then GG contains a rainbow path of length d1d-1.

The source says this conjecture strengthens an earlier conjecture of Andersen and that the directed question discussed immediately before it is a significant strengthening. It also notes that Schrijver's conjecture has been asymptotically resolved, but does not state that the exact conjecture is solved.

Sources & referencesView supporting material

Primary source

Nicholas Crawford, Maya Sankar, Carl Schildkraut and Sam Spiro, “Rainbow Trees in Hypercubes”, arXiv:2508.14186 (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.