Čada–Kaneko–Ryjáček conjecture on minimum color degree and rainbow cycles

Let GG be an edge-colored graph with n=V(G)n=|V(G)| vertices, and let δc(G)\delta^c(G) denote its minimum color degree. For an integer kk, a rainbow cycle is a cycle whose edges have pairwise distinct colors.

Čada–Kaneko–Ryjáček conjecture. If

δc(G)n+k2,\delta^c(G)\geq \frac{n+k}{2},

then GG contains a rainbow-cycle subgraph of length at least kk.

This conjecture generalizes the known sufficient condition that δc(G)>n2+2\delta^c(G)>\frac{n}{2}+2 guarantees a rainbow cycle of length at least four. The source does not provide evidence that the conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Wipawee Tangjai, “The minimum color degree and a large rainbow cycle in an edge-colored graph”, arXiv:1708.04187 (2017).

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.