Directed graphs without rainbow triangles

EUROCOMB’23

Abstract
One of the most fundamental questions in graph theory is Mantel‘s theorem which determines the maximum number of edges in a triangle-free graph of a given order. Recently a colorful variant of this problem has been solved. In such a variant we consider $c$ graphs on a common vertex set, thinking of each graph as edges in a distinct color, and want to determine the smallest number of edges in each color which guarantees the existence of a rainbow triangle. Here, we solve the analogous problem for directed graphs without rainbow triangles, either directed or transitive, for any number of colors. The constructions and proofs essentially differ for $c=3$ and $c \geq 4$ and the type of the forbidden triangle.

Pages:
88–93
Metrics

0

Views

0

PDF views