{
  "id": "1806.00825",
  "version": "v1",
  "published": "2018-06-03T16:27:11.000Z",
  "updated": "2018-06-03T16:27:11.000Z",
  "title": "Short rainbow cycles in sparse graphs",
  "authors": [
    "Matt DeVos",
    "Sebastián González Hermosillo de la Maza",
    "Krystal Guo",
    "Daryl Funk",
    "Tony Huynh",
    "Bojan Mohar",
    "Amanda Montejano"
  ],
  "comment": "6 pages, 2 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Let $G$ be a simple $n$-vertex graph and $c$ be a colouring of $E(G)$ with $n$ colours, where each colour class has size at least $2$. We prove that $G$ contains a rainbow cycle of length at most $\\lceil \\frac{n}{2} \\rceil$, which is best possible. Our result settles a special case of a strengthening of the Caccetta-H\\\"aggkvist conjecture, due to Aharoni. We also show that the matroid generalization of our main result also holds for cographic matroids, but fails for binary matroids.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-06-03T16:27:11.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C20",
      "05C38"
    ],
    "keywords": [
      "short rainbow cycles",
      "sparse graphs",
      "colour class",
      "matroid generalization",
      "main result"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}