Aharoni's rainbow cycle conjecture holds up to an additive constant

Abstract

In 2017, Aharoni proposed the following generalization of the Caccetta-Häggkvist conjecture: if $G$ is a simple $n$-vertex edge-colored graph with $n$ color classes of size at least $r$, then $G$ contains a rainbow cycle of length at most $\lceil n/r\rceil$. In this paper, we prove that, for fixed $r$, Aharoni's conjecture holds up to an additive constant. Specifically, we show that for each fixed $r\ge 1$, there exists a constant $\hat{I}{\pm }_r\in O(r^5{\log }^{2}r)$ such that if $G$ is a simple $n$-vertex edge-colored graph with $n$ color classes of size at least $r$, then $G$ contains a rainbow cycle of length at most $n/r+\hat{I}{\pm }_r$.

11 pages, 1 figure