Aharoni's rainbow Caccetta–Häggkvist conjecture

At least 10 years old · documented by

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.

References

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.