Disjoint matchings of graphs
| Autor: | Kenneth Lebensold |
|---|---|
| Jazyk: | angličtina |
| Předmět: | |
| Zdroj: | Journal of Combinatorial Theory, Series B. (3):207-210 |
| ISSN: | 0095-8956 |
| DOI: | 10.1016/0095-8956(77)90066-1 |
| Popis: | In this paper, we prove a generalization of the familiar marriage theorem. One way of stating the marriage theorem is: Let G be a bipartite graph, with parts S 1 and S 2 . If A ⊂ S 1 and F ( A ) ⊂ S 2 is the set of neighbors of points in A , then a matching of G exists if and only if Σ x ∈ S 2 min(1, | F −1 ( x ) ∩ A |) ≥ | A | for each A ⊂ S 1 . Our theorem is that k disjoint matchings of G exist if and only Σ x ∈ S 2 min ( k , | F −1 ( x ) ∩ A |) ≥ k | A | for each A ⊂ S 1 . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|