Abstract:

The famous Caccetta-Häggkvist conjecture states that for any n-vertex directed graph D, the directed girth of D (the minimum length of a directed cycle in D) is at most \lceil n/k \rceil, where k is the minimum out-degree of D. Aharoni raised a strengthening conjecture: for any n-vertex graph G equipped with an edge coloring (not necessarily proper) using n colors, the rainbow girth of G (the minimum length of a cycle in G with distinctly colored edges) is at most \lceil n/k \rceil, where k is the minimum size of the color class. We will discuss some results in the non-uniform degrees and rainbow versions of the Caccetta-Häggkvist conjecture.

Based on works joint with Ron Aharoni, Eli Berger, Maria Chudnovsky, and Shira Zerbib.