{
  "id": "2308.01461",
  "version": "v1",
  "published": "2023-08-02T22:29:02.000Z",
  "updated": "2023-08-02T22:29:02.000Z",
  "title": "Directed graphs without rainbow triangles",
  "authors": [
    "Sebastian Babiński",
    "Andrzej Grzesik",
    "Magdalena Prorok"
  ],
  "comment": "20 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "One of the most fundamental results in graph theory is Mantel's theorem which determines the maximum number of edges in a triangle-free graph of order $n$. 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 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. Additionally, we also solve the analogous problem in the setting of oriented graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-08-02T22:29:02.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C20",
      "05C35"
    ],
    "keywords": [
      "rainbow triangle",
      "directed graphs",
      "common vertex set",
      "analogous problem",
      "triangle-free graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}