{
  "id": "2011.01592",
  "version": "v1",
  "published": "2020-11-03T09:48:14.000Z",
  "updated": "2020-11-03T09:48:14.000Z",
  "title": "The Erdős-Gyárfás function with respect to Gallai-colorings",
  "authors": [
    "Xihe Li",
    "Hajo Broersma",
    "Ligong Wang"
  ],
  "comment": "25 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "For fixed $p$ and $q$, an edge-coloring of the complete graph $K_n$ is said to be a $(p, q)$-coloring if every $K_p$ receives at least $q$ distinct colors. The function $f(n, p, q)$ is the minimum number of colors needed for $K_n$ to have a $(p, q)$-coloring. This function was introduced about 45 years ago, but was studied systematically by Erd\\H{o}s and Gy\\'{a}rf\\'{a}s in 1997, and is now known as the Erd\\H{o}s-Gy\\'{a}rf\\'{a}s function. In this paper, we study $f(n, p, q)$ with respect to Gallai-colorings, where a Gallai-coloring is an edge-coloring of $K_n$ without rainbow triangles. Combining the two concepts, we consider the function $g(n, p, q)$ that is the minimum number of colors needed for a Gallai-$(p, q)$-coloring of $K_n$. Using the anti-Ramsey number for $K_3$, we have that $g(n, p, q)$ is nontrivial only for $2\\leq q\\leq p-1$. We give a general lower bound for this function and we study how this function falls off from being equal to $n-1$ when $q=p-1$ and $p\\geq 4$ to being $O(\\log n)$ when $q = 2$. In particular, for appropriate $p$ and $n$, we prove that $g=n-c$ when $q=p-c$ and $c\\in \\{1,2\\}$, $g$ is at most a fractional power of $n$ when $q=\\lfloor\\sqrt{p-1}\\rfloor$, and $g$ is logarithmic in $n$ when $2\\leq q\\leq \\lfloor\\log_2 (p-1)\\rfloor+1$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-11-03T09:48:14.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C55",
      "05D10"
    ],
    "keywords": [
      "erdős-gyárfás function",
      "minimum number",
      "gallai-coloring",
      "general lower bound",
      "distinct colors"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}