Notes on Aharoni's rainbow cycle conjecture
share
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 ⌈n/r⌉. 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 4n/9+7. We also discuss how our approach might generalise to larger values of r.
READ FULL TEXT