Graph Theory and Combinatorics Seminar

Title: Bounds on the triangle case of Aharoni's rainbow cycle conjecture

Abstract: Aharoni proposed a generalization of the Caccetta--H\"aggkvist conjecture in which one colors the edges of an undirected graph and seek to find a short rainbow cycle. Formally, if one colors the edges of an $n$ vertex graph with n colors, each color class having size at least $n/r$, then is there always a rainbow cycle of length at most $r$? We will consider the following version of the problem. For which $\alpha$ and $\beta$ does it suffice to have $\alpha n$ color classes (coloring edges) each of size at least $\beta n$ to guarantee a rainbow triangle? In this talk we discuss the main ideas in the best known results for $(\alpha, \beta)$ tuples that produce a rainbow triangle.

Joint work with Patrick Hompe and Sophie Spirkl.