Rainbow triangles and the Caccetta‐Häggkvist conjecture. Issue 4 (18th March 2019)

• Record Type: Journal Article
• Authors: Aharoni, Ron; DeVos, Matthew; Holzman, Ron
• Is Part Of: Journal of graph theory. Volume 92:Issue 4(2019)
• Page Start: 347
• Page End: 360
• Publication Date: 2019-03-18
• Subjects: Caccetta‐Häggkvist -- edge‐colored graph -- rainbow triangles; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22457
• Languages: English
• ISSNs: 0364-9024

Abstract

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.