Premium
Rainbow triangles and the Caccetta‐Häggkvist conjecture
Author(s) -
Aharoni Ron,
DeVos Matthew,
Holzman Ron
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22457
Subject(s) - combinatorics , mathematics , rainbow , conjecture , digraph , vertex (graph theory) , disjoint sets , generalization , graph , discrete mathematics , physics , mathematical analysis , quantum mechanics
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.