1. Perfect matchings in -partite -graphs
- Author
-
Aharoni, Ron, Georgakopoulos, Agelos, and Sprüssel, Philipp
- Subjects
- *
MATCHING theory , *GRAPH theory , *COMBINATORICS , *MATHEMATICAL analysis , *NUMERICAL analysis , *GRAPHIC methods - Abstract
Abstract: Let be an -partite -graph, all of whose sides have the same size . Suppose that there exist two sides of , each satisfying the following condition: the degree of each legal -tuple contained in the complement of this side is strictly larger than . We prove that under this condition must have a perfect matching. This answers a question of Kühn and Osthus. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF