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

Patrick Hompe¹ ; Sophie Spirkl¹

¹University of Waterloo

The electronic journal of combinatorics, Tome 29 (2022) no. 1

Résumé

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.

Détail

DOI : 10.37236/10418

Classification : 05C38, 05C15, 05C20, 05C12
Mots-clés : Aharoni's conjecture, Caccetta-Haggkvist conjecture, rainbow cycle, directed cycle