Short rainbow cycles in graphs and matroids

Abstract

Let $G$ be a simple $n$-vertex graph and $c$ be a colouring of $E(G)$ with $n$ colours, where each colour class has size at least $2$. We prove that $(G,c)$ contains a rainbow cycle of length at most $\lceil \frac{n}{2}\rceil$, which is best possible. Our result settles a special case of a strengthening of the Caccetta-Häggkvist conjecture, due to Aharoni. We also show that the matroid generalization of our main result also holds for cographic matroids, but fails for binary matroids.

9 pages, 2 figures. In this version we correct a slight inaccurancy in the proof of Theorem 14, found by the pilot project Mathpocalypse (https://github.com/natema/mathpocalypse-project) of Emanuele Natale and Édouard Oyallon

References in corpus (2)

• Counting flags in triangle-free digraphs
• A Summary of Problems and Results related to the Caccetta-Haggkvist Conjecture