## Matching TheoryThis study of matching theory deals with bipartite matching, network flows, and presents fundamental results for the non-bipartite case. It goes on to study elementary bipartite graphs and elementary graphs in general. Further discussed are 2-matchings, general matching problems as linear programs, the Edmonds Matching Algorithm (and other algorithmic approaches), f-factors and vertex packing. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 | |

Chapter 2 Flow theory | 41 |

Chapter 3 Size and structure of maximum matchings | 83 |

Chapter 4 Bipartite graphs with perfect matchings | 121 |

Chapter 5 General graphs with perfect matchings | 143 |

Chapter 6 Some graphtheoretical problems related to matchings | 213 |

Chapter 7 Matching and linear programming | 255 |

Chapter 8 Determinants and matchings | 307 |

Chapter 9 Matching algorithms | 357 |

Chapter 10 The ffactor problem | 383 |

Chapter 11 Matroid matching | 409 |

Chapter 12 Vertex packing and covering | 443 |

References | 483 |

527 | |

539 | |

### Other editions - View all

### Common terms and phrases

1-extendable 2-matching 2-polymatroid adjacent assume bicritical graphs bigraph bipartite graph called characterization chromatic index Claim color combinatorial complete graph components of G Comput contradiction Corollary def(G defined denote ear decomposition Edmonds elementary bipartite graph elementary graph endpoints EXERCISE exists f-factor factor-critical graphs finite flow formulated G contains Gallai-Edmonds graph G graph theory hence hypergraph independent set inequalities integer joining König König's Theorem Lemma Let G linear programming lines of G Lovász Marriage Theorem matching algorithm matching in G matching of G matching polytope matching problem matching theory Math matrix matroid maximum matching minimal elementary Minimax Theorem non-bipartite non-negative NP-complete number of lines number of points obtain odd cycle partition path perfect graphs perfect matching planar graphs PM(G point cover points of G polynomial polytope prove result set of points spanning subgraph H subgraph of G submodular subset T-critical graph T-cuts T-join trivial