{
  "id": "2006.04879",
  "version": "v1",
  "published": "2020-06-08T19:00:23.000Z",
  "updated": "2020-06-08T19:00:23.000Z",
  "title": "Extremal problems and results related to Gallai-colorings",
  "authors": [
    "Xihe Li",
    "Hajo Broersma",
    "Ligong Wang"
  ],
  "comment": "20 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "A Gallai-coloring (Gallai-$k$-coloring) is an edge-coloring (with colors from $\\{1, 2, \\ldots, k\\}$) of a complete graph without rainbow triangles. Given a graph $H$ and a positive integer $k$, the $k$-colored Gallai-Ramsey number $GR_k(H)$ is the minimum integer $n$ such that every Gallai-$k$-coloring of the complete graph $K_n$ contains a monochromatic copy of $H$. In this paper, we prove that for any positive integers $d$ and $k$, there exists a constant $c$ such that if $H$ is an $n$-vertex graph with maximum degree $d$, then $GR_k(H)$ is at most $cn$. We also determine $GR_k(K_4+e)$ for the graph on 5 vertices consisting of a $K_4$ with a pendant edge. Furthermore, we consider two extremal problems related to Gallai-$k$-colorings. For $n\\geq GR_k(K_3)$, we determine upper and lower bounds for the minimum number of monochromatic triangles in a Gallai-$k$-coloring of $K_{n}$, implying that this number is $O(n^3)$ and yielding the exact value for $k=3$. We also determine upper and lower bounds for the maximum number of edges that are not contained in any rainbow triangle or monochromatic triangle in a $k$-edge-coloring of $K_n$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-06-08T19:00:23.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C35",
      "05C55",
      "05D10"
    ],
    "keywords": [
      "extremal problems",
      "rainbow triangle",
      "lower bounds",
      "determine upper",
      "complete graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}