Graph factors |
| |
Authors: | W T Tutte |
| |
Institution: | (1) Dept. of Comb. and Opt., University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada |
| |
Abstract: | This exposition is concerned with the main theorems of graph-factor theory, Hall’s and Ore’s Theorems in the bipartite case,
and in the general case Petersen’s Theorem, the 1-Factor Theorem and thef-Factor Theorem. Some published extensions of these theorems are discussed and are shown to be consequences rather than generalizations
of thef-Factor Theorem. The bipartite case is dealt with in Section 2. For the proper presentation of the general case a preliminary
theory of “G-triples” and “f-barriers” is needed, and this is set out in the next three Sections. Thef-Factor Theorem is then proved by an argument of T. Gallai in a generalized form. Gallai’s original proof derives the 1-Factor
Theorem from Hall’s Theorem. The generalization proceeds analogously from Ore’s Theorem to thef-Factor Theorem. |
| |
Keywords: | 05 C 99 |
本文献已被 SpringerLink 等数据库收录! |
|