{
  "id": "1901.03308",
  "version": "v1",
  "published": "2019-01-10T18:23:00.000Z",
  "updated": "2019-01-10T18:23:00.000Z",
  "title": "Lower bounds for rainbow Turán numbers of paths and other trees",
  "authors": [
    "Daniel Johnston",
    "Puck Rombach"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "For a fixed graph $F$, we would like to determine the maximum number of edges in a properly edge-colored graph on $n$ vertices which does not contain a rainbow copy of $F$, that is, a copy of $F$ all of whose edges receive a different color. This maximum, denoted by $ex^*(n, F)$, is the rainbow Tur\\'{a}n number of $F$. We show that $ex^*(n,P_k)\\geq \\frac{k}{2}n + O(1)$ where $P_k$ is a path on $k\\geq 3$ edges, generalizing a result by Maamoun and Meyniel and by Johnston, Palmer and Sarkar. We show similar bounds for brooms on $2^s-1$ edges and diameter $\\leq 10$ and a few other caterpillars of small diameter.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-01-10T18:23:00.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C35",
      "05C38"
    ],
    "keywords": [
      "rainbow turán numbers",
      "lower bounds",
      "maximum number",
      "small diameter",
      "similar bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}