{
  "id": "1905.04657",
  "version": "v1",
  "published": "2019-05-12T06:39:06.000Z",
  "updated": "2019-05-12T06:39:06.000Z",
  "title": "Long monochromatic paths and cycles in 2-edge-colored multipartite graphs",
  "authors": [
    "József Balogh",
    "Alexandr Kostochka",
    "Mikhail Lavrov",
    "Xujun Liu"
  ],
  "comment": "46 pages, 4 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "We solve four similar problems: For every fixed $s$ and large $n$, we describe all values of $n_1,\\ldots,n_s$ such that for every $2$-edge-coloring of the complete $s$-partite graph $K_{n_1,\\ldots,n_s}$ there exists a monochromatic (i) cycle $C_{2n}$ with $2n$ vertices, (ii) cycle $C_{\\geq 2n}$ with at least $2n$ vertices, (iii) path $P_{2n}$ with $2n$ vertices, and (iv) path $P_{2n+1}$ with $2n+1$ vertices. This implies a generalization for large $n$ of the conjecture by Gy\\'arf\\'as, Ruszink\\'o, S\\'ark\\H{o}zy and Szemer\\'edi that for every $2$-edge-coloring of the complete $3$-partite graph $K_{n,n,n}$ there is a monochromatic path $P_{2n+1}$. An important tool is our recent stability theorem on monochromatic connected matchings.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-05-12T06:39:06.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C35",
      "05C38"
    ],
    "keywords": [
      "long monochromatic paths",
      "multipartite graphs",
      "similar problems",
      "important tool",
      "stability theorem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 46,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}