Aharoni's rainbow Caccetta–Häggkvist conjecture
Let be an -vertex graph whose edges are colored with colors, and let the rainbow girth be the minimum length of a rainbow cycle, with value if no rainbow cycle exists. Assume that every color class has size at least . Aharoni's rainbow Caccetta–Häggkvist conjecture. The rainbow girth of is at most
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
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.
Source: He Guo, “Short rainbow cycles for families of small edge sets”, arXiv:2507.04581 (2025).
Progress summary
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.