Degree Sequences and the Existence of k-Factors

• Published in: Graphs and combinatorics 2012-03, Vol.28 (2), p.149-166
• Main Authors: Bauer, D., Broersma, H. J., van den Heuvel, J., Kahl, N., Schmeichel, E.
• Format: Article
• Language: English
• Subjects: Algorithms; Combinatorial analysis; Combinatorics; Complexity; Engineering Design; Graphs; Mathematics; Mathematics and Statistics; Original Paper; Strength; Theorems; Tightness
• ISSN: 0911-0119; 1435-5914
• DOI: 10.1007/s00373-011-1044-z

We consider sufficient conditions for a degree sequence π 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 π to be forcibly 1-factor graphical and, more generally, forcibly graphical with deficiency at most β  ≥ 0. These theorems are equal in strength to Chvátal’s well-known hamiltonian theorem, i.e., the best monotone degree condition for hamiltonicity. We then give an equally strong theorem for π 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 π to be forcibly k -factor graphical whose algorithmic complexity grows more slowly. In the final section, we present such a theorem for any k  ≥ 2, 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.