Aharoni's rainbow Caccetta–Häggkvist conjecture
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.