Keevash–Mubayi–Sudakov–Verstraëte rainbow-cycle conjecture

About 2 years old · traced to

Let GG be a properly edge-colored graph on nn vertices, meaning that no two edges incident with the same vertex have the same color. A rainbow cycle is a cycle whose edges all have distinct colors.

Keevash–Mubayi–Sudakov–Verstraëte conjecture. There is a constant CC such that every properly edge-colored nn-vertex graph with at least Cnlog⁡nCn\log n edges contains a rainbow cycle.

The statement is motivated by a construction with Ω(nlog⁡n)\Omega(n\log n) edges and is presented as the conjectured sharp order of magnitude. Its resolution is not given in the supplied text.

References

Primary source

Benny Sudakov, “Restricted subgraphs of edge-colored graphs and applications”, arXiv:2412.13945 (2024).

Additional references

2 papers in this index state this conjecture (2024). The statement above is taken from the most recent of them; the others are arXiv:2401.10865.

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.