Further Approximations for Aharoni's Rainbow Generalization of the Caccetta-Häggkvist Conjecture

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$. 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 ${\Omega}(k\log k)$. In this paper, we present a proof of the conjecture if each color class has size ${\Omega}(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.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.