### Abstract

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.

Original language | Undefined |
---|---|

Pages (from-to) | 149-166 |

Number of pages | 18 |

Journal | Graphs and combinatorics |

Volume | 28 |

Issue number | 2 |

DOIs | |

Publication status | Published - Mar 2012 |

### Keywords

- k-Factor
- EWI-22742
- MSC-05C
- Best monotone condition
- METIS-296437
- IR-83470
- Degree sequence

## Cite this

Bauer, D., Broersma, H. J., van den Heuvel, J., Kahl, N., & Schmeichel, E. (2012). Degree sequences and the existence of k-factors.

*Graphs and combinatorics*,*28*(2), 149-166. https://doi.org/10.1007/s00373-011-1044-z