Notes on Aharoni’s rainbow cycle conjecture

In 2017, Ron Aharoni made the following conjecture about rainbow cycles in edge-coloured graphs: If G is an n-vertex graph whose edges are coloured with n colours and each colour class has size at least r, then G contains a rainbow cycle of length at most \(\left\lceil \frac{n}{r} \right\rceil \) . . One motivation for studying Aharoni’s conjecture is that it is a strengthening of the Caccetta-Häggkvist conjecture on digraphs from 1978. In this article, we present a survey of Aharoni’s conjecture, including many recent partial results and related conjectures. We also present two new results. Our first result (Theorem 21) provides sharp thresholds for rainbow cycles in edge-coloured graphs with 3 colours. Our second, and main, result (Theorem 35) is for the r = 3 case of Aharoni’s conjecture. We prove that if G is an n-vertex graph whose edges are coloured with n colours and each colour class has size at least 3, then G contains a rainbow cycle of length at most \(\frac{4n}{9} + 1\) .