{
  "id": "1602.02461",
  "version": "v1",
  "published": "2016-02-08T04:06:45.000Z",
  "updated": "2016-02-08T04:06:45.000Z",
  "title": "Strengthening theorems of Dirac and Erdős on disjoint cycles",
  "authors": [
    "Henry A. Kierstead",
    "Alexandr V. Kostochka",
    "Andrew McConvey"
  ],
  "comment": "13 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $k \\ge 3$ be an integer, $H_{k}(G)$ be the set of vertices of degree at least $2k$ in a graph $G$, and $L_{k}(G)$ be the set of vertices of degree at most $2k-2$ in $G$. In 1963, Dirac and Erd\\H{o}s proved that $G$ contains $k$ (vertex-)disjoint cycles whenever $|H_{k}(G)| - |L_{k}(G)| \\ge k^{2} + 2k - 4$. The main result of this paper is that for $k \\ge 2$, every graph $G$ with $|V(G)| \\ge 3k$ containing at most $t$ disjoint triangles and with $|H_{k}(G)| - |L_{k}(G)| \\ge 2k + t$ contains $k$ disjoint cycles. This yields that if $k \\ge 2$ and $|H_{k}(G)| - |L_{k}(G)| \\ge 3k$, then $G$ contains $k$ disjoint cycles. This generalizes the Corr\\'{a}di-Hajnal Theorem, which states that every graph $G$ with $H_{k}(G) = V(G)$ and $|H_{k}(G)| \\ge 3k$ contains $k$ disjoint cycles.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-02-08T04:06:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C70",
      "05C10"
    ],
    "keywords": [
      "disjoint cycles",
      "strengthening theorems",
      "disjoint triangles",
      "main result",
      "generalizes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160202461K"
    }
  }
}