Rainbow triangles and the Caccetta‐Häggkvist conjecture. Issue 4 (18th March 2019) - Aharoni, Ron; DeVos, Matthew; Holzman, Ron
Abstract: A famous conjecture of Caccetta and Häggkvist is that in a digraph on n vertices and minimum outdegree at least n / r there is a directed cycle of length r or less. We consider the following generalization: in an undirected graph on n vertices, any collection of n disjoint sets of edges, each of size at least n / r, has a rainbow cycle of length r or less. We focus on the case r = 3 and prove the existence of a rainbow triangle under somewhat stronger conditions than in the conjecture. In our main result, whenever n is larger than a suitable polynomial in k, we determine the maximum number of edges in an n ‐vertex edge‐colored graph where all color classes have size at most k and there is no rainbow triangle. Moreover, we characterize the extremal graphs for this problem.