Aharoni's rainbow Caccetta–Häggkvist conjecture

Let GG be an nn-vertex graph whose edges are colored with nn colors, and let the rainbow girth be the minimum length of a rainbow cycle, with value \infty if no rainbow cycle exists. Assume that every color class has size at least rr. Aharoni's rainbow Caccetta–Häggkvist conjecture. The rainbow girth of GG is at most

nr.\left\lceil\frac{n}{r}\right\rceil.

This conjecture generalizes the Caccetta–Häggkvist conjecture to edge-colored graphs. The supplied text does not state whether it has been resolved; the surrounding paper studies sufficient conditions for logarithmic rainbow girth.

Sources & referencesView supporting material

Primary source

He Guo, “Short rainbow cycles for families of small edge sets”, arXiv:2507.04581 (2025).

Additional references

11 papers in this index state this conjecture (2015–2025). The statement above is taken from the most recent of them; the others are arXiv:2311.12302, arXiv:2212.05697, arXiv:2211.07897, arXiv:2206.10733, arXiv:2105.03373, arXiv:2101.04716, arXiv:1812.11872, arXiv:1806.00825, arXiv:1709.02665, arXiv:1505.01779.

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.