Name
Abstract | ||
|---|---|---|
A famous conjecture of Caccetta and Haggkvist 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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1002/jgt.22457 | JOURNAL OF GRAPH THEORY |
Keywords | DocType | Volume |
Caccetta-Haggkvist,edge-colored graph,rainbow triangles | Journal | 92.0 |
Issue | ISSN | Citations |
4.0 | 0364-9024 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ron Aharoni I | 1 | 13 | 8.92 |
| Matthew DeVos | 2 | 0 | 0.34 |
| Ron Holzman | 3 | 287 | 43.78 |