Rainbow directed cycle-or-path conjecture for proper arc-colourings

Let Kn\overleftrightarrow{K_n} be the digraph obtained from the complete graph KnK_n by replacing each edge with two oppositely directed arcs and adding a directed loop at each vertex. A proper arc-colouring is a colouring in which no two arcs of the same colour have a common head or a common tail. Rainbow directed cycle-or-path conjecture. Every proper arc-colouring of Kn\overleftrightarrow{K_n} admits a rainbow directed cycle or path of length at least n1n-1. This conjecture is motivated by bounds for rainbow directed cycles and by the study of connected rainbow subgraphs with maximum in-degree and out-degree at most one; it remains open.

Sources & referencesView supporting material

Primary source

Stephen Gould and Tom Kelly, “Hamilton transversals in random Latin squares”, arXiv:2104.12718 (2022).

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.