Notes on Aharoni's rainbow cycle conjecture

Abstract

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 $\lceil \frac{n}{r}\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 main new result 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}+7$. We also discuss how our approach might generalise to larger values of $r$.

12 pages, 0 figures. Minor changes. Also added an exact result for the 3 colour case of Question 2.5