{
  "id": "0912.2916",
  "version": "v2",
  "published": "2009-12-15T15:00:36.000Z",
  "updated": "2011-03-08T18:14:59.000Z",
  "title": "Degree Sequences and the Existence of $k$-Factors",
  "authors": [
    "D. Bauer",
    "H. J. Broersma",
    "J. van den Heuvel",
    "N. Kahl",
    "E. Schmeichel"
  ],
  "comment": "19 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We consider sufficient conditions for a degree sequence $\\pi$ to be forcibly $k$-factor graphical. We note that previous work on degrees and factors has focused primarily on finding conditions for a degree sequence to be potentially $k$-factor graphical. We first give a theorem for $\\pi$ to be forcibly 1-factor graphical and, more generally, forcibly graphical with deficiency at most $\\beta\\ge0$. These theorems are equal in strength to Chv\\'atal's well-known hamiltonian theorem, i.e., the best monotone degree condition for hamiltonicity. We then give an equally strong theorem for $\\pi$ to be forcibly 2-factor graphical. Unfortunately, the number of nonredundant conditions that must be checked increases significantly in moving from $k=1$ to $k=2$, and we conjecture that the number of nonredundant conditions in a best monotone theorem for a $k$-factor will increase superpolynomially in $k$. This suggests the desirability of finding a theorem for $\\pi$ to be forcibly $k$-factor graphical whose algorithmic complexity grows more slowly. In the final section, we present such a theorem for any $k\\ge2$, based on Tutte's well-known factor theorem. While this theorem is not best monotone, we show that it is nevertheless tight in a precise way, and give examples illustrating this tightness.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-03-08T18:14:59.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C70",
      "05C07"
    ],
    "keywords": [
      "degree sequence",
      "tuttes well-known factor theorem",
      "factor graphical",
      "best monotone degree condition",
      "nonredundant conditions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0912.2916B"
    }
  }
}