On Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture

Abstract

For a digraph $G$ and $v\in V(G)$, let ${\delta }^{+}(v)$ be the number of out-neighbors of $v$ in $G$. The Caccetta-Häggkvist conjecture states that for all $k\ge 1$, if $G$ is a digraph with $n=|V(G)|$ such that ${\delta }^{+}(v)\ge k$ for all $v\in V(G)$, then G contains a directed cycle of length at most $\lceil n/k\rceil$. In [2], Aharoni proposes a generalization of this conjecture, that a simple edge-colored graph on $n$ vertices with $n$ color classes, each of size $k$, has a rainbow cycle of length at most $\lceil n/k\rceil$. In this paper, we prove this conjecture if each color class has size $\Omega (k\log k)$.

Accepted manuscript. See DOI for journal version. arXiv admin note: text overlap with arXiv:2105.03373