Non-uniform degrees and rainbow versions of the Caccetta-Häggkvist conjecture

Abstract

The Caccetta-Häggkvist conjecture (denoted below CHC) states that the directed girth (the smallest length of a directed cycle) $dgirth(D)$ of a directed graph $D$ on $n$ vertices is at most $\lceil \frac{n}{\hat{I}{´}^{+}(D)}\rceil$, where $\hat{I}{´}^{+}(D)$ is the minimum out-degree of~$D$. We consider a version involving all out-degrees, not merely the minimum one, and prove that if $D$ does not contain a sink, then $dgirth(D)\le 2{\sum }_{v\in V(D)}\frac{1}{de{g}^{+}(v)+1}$. In the spirit of a generalization of the CHC to rainbow cycles in \cite{ADH2019}, this suggests the conjecture that given non-empty sets $F_1,\dots ,F_n$ of edges of $K_n$, there exists a rainbow cycle of length at most $2{\sum }_{1\le i\le n}\frac{1}{|F_i|+1}$. We prove a bit stronger result when $1\le |F_i|\le 2$, thereby strengthening a result of DeVos et. al \cite{DDFGGHMM2021}. We prove a logarithmic bound on the rainbow girth in the case that the sets $F_i$ are triangles.