{
  "id": "2409.03394",
  "version": "v1",
  "published": "2024-09-05T10:06:41.000Z",
  "updated": "2024-09-05T10:06:41.000Z",
  "title": "Partitioning 2-edge-coloured bipartite graphs into monochromatic cycles",
  "authors": [
    "Fabrício Siqueira Benevides",
    "Arthur Lima Quintino",
    "Alexandre Talon"
  ],
  "comment": "17 pages, 21 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Given an $r$-colouring of the edges of a graph $G$, we say that it can be partitioned into $p$ monochromatic cycles when there exists a set of $p$ vertex-disjoint monochromatic cycles covering all the vertices of $G$. In the literature of this problem, an edge and a single vertex both count as a cycle. We show that for every $2$-colouring of the edges of a complete balanced bipartite graph, $K_{n,n}$, it can be partitioned into at most 4 monochromatic cycles. This type of question was first studied in 1970 for complete graphs and in 1983, by Gy\\'arf\\'as and Lehel, for $K_{n,n}$. In 2014, Pokrovskiy, has showed that any $2$-colouring of the edges of $K_{n,n}$ can be partitioned into at most $3$ paths. It turns out that finding monochromatic cycles instead of paths is a natural question that has also being asked for other graphs. In 2015, Schaudt and Stein have showed that at most 14 cycles are necessary.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-09-05T10:06:41.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C35",
      "05C70",
      "G.2.2"
    ],
    "keywords": [
      "complete balanced bipartite graph",
      "vertex-disjoint monochromatic cycles covering",
      "complete graphs",
      "partitioning",
      "finding monochromatic cycles"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}