A famous conjecture of Caccetta and H"aggkvist is that in a digraph on vertices and minimum out-degree at least there is a directed cycle of length or less. We consider the following generalization: in an undirected graph on vertices, any collection of disjoint sets of edges, each of size at least , has a rainbow cycle of length or less. We focus on the case , and prove the existence of a rainbow triangle under somewhat stronger conditions than in the conjecture. For any fixed and large enough , we determine the maximum number of edges in an -vertex edge-coloured graph where all colour classes have size at most and there is no rainbow triangle. Moreover, we characterize the extremal graphs for this problem.

生成讲解博客的中文版本

生成AI智能校验的中文版本