Directed graphs without rainbow triangles
EUROCOMB’23
Abstract
Pages:
88–93
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.
88–93
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Sebastian Babiński, Andrzej Grzesik, Magdalena Prorok