{
  "id": "1902.05882",
  "version": "v1",
  "published": "2019-02-15T16:40:36.000Z",
  "updated": "2019-02-15T16:40:36.000Z",
  "title": "Minimum degree conditions for monochromatic cycle partitioning",
  "authors": [
    "Dániel Korándi",
    "Richard Lang",
    "Shoham Letzter",
    "Alexey Pokrovskiy"
  ],
  "comment": "23 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A classical result of Erd\\H{o}s, Gy\\'ar\\'as and Pyber states that any $r$-edge-coloured complete graph has a partition into $O(r^2 \\log r)$ monochromatic cycles. Here we determine the minimum degree threshold for this property. More precisely, we show that there exists a constant c such that any $r$-edge-coloured graph on $n$ vertices with minimum degree at least $n/2 + c \\cdot r \\log n$ has a partition into $O(r^2)$ monochromatic cycles. We also provide constructions showing that the minimum degree condition and the number of cycles are essentially tight.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-02-15T16:40:36.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "minimum degree condition",
      "monochromatic cycle partitioning",
      "minimum degree threshold",
      "edge-coloured complete graph",
      "pyber states"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}