Ryser's conjecture on rainbow cycle packings

About 3 years old · traced to

Let K⃗n\vec{K}_n be the complete directed graph with both directed edges between every pair of vertices and a loop at every vertex, properly edge-coloured with nn colours. A rainbow spanning subgraph is one whose edges have distinct colours.

Ryser's conjecture. If nn is odd, then K⃗n\vec{K}_n contains a rainbow spanning subgraph in which every vertex has in-degree and out-degree equal to one. Equivalently, K⃗n\vec{K}_n can be packed with directed cycles in a rainbow fashion.

This is a conjecture about rainbow cycle decompositions of properly coloured complete directed graphs. The paper presents it as a famous open problem and discusses related strengthening by prescribing cycle lengths.

References

Primary source

Alp Müyesser, “Cycle type in Hall-Paige: A proof of the Friedlander-Gordon-Tannenbaum conjecture”, arXiv:2303.16157 (2023).

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.