2022/11/15 by Katie Clinch, Clinch, Katie, Jackson Goerner +5 · 1 citation
Computer Science · Mathematics · #05B35 #05C15 #05C20 #05C35 #05C38 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2211.07897
openalex publication_date 2022/11/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (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 (4n)/(9)+7. We also discuss how our approach might generalise to larger values of r.