Further approximations for Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture

Abstract

For a digraph $G$ and $v\in V(G)$, let $\hat{I}{´}^{+}(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 $\hat{I}{´}^{+}(v)\ge k$ for all $v\in V(G)$, then $G$ contains a directed cycle of length at most $\lceil n/k\rceil$. Aharoni proposed 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$. With Pelikánová and Pokorná, we showed that this conjecture is true if each color class has size $\hat{I}\text{c◯}(k\log k)$. In this paper, we present a proof of the conjecture if each color class has size $\hat{I}\text{c◯}(k)$, which improved the previous result and is only a constant factor away from Aharoni's conjecture. We also consider what happens when the condition on the number of colors is relaxed.

Updating paper with added corrigendum section fixing error in earlier version