Matching theory (Q1088987): Difference between revisions

The theory of matchings in graphs is one of the most mature parts of Combinatorics. There is an extensive body of results, bounded by a number of deep open problems. This book is the first devoted to the topic, and is written by two acknowledged experts in the field. For these reasons alone, it is clear that it will repay careful study. Although attention is always focused on matchings, a broad range of related topics are covered, and many exercises are provided. (These vary widely in difficulty. Generally no hints or solutions are provided.) There are altogether twelve chapters. The first is on matchings in bipartite graphs, the second on flows and the third considers Tutte's theorem, the Gallai-Edmonds structure theorem and related topics. This is all material that might well be covered in a first serious course in Graph Theory. The next two chapters cover the structure of graphs with a perfect matching. This is deeper material, and is an area where considerable development is still taking place. The remaining chapters cover such topics as 2-matchings, linear programming, determinants and matchings, f-factors and vertex covering and packing. There is also a considerable amount of material devoted to algorithmic questions, and to matroids. The chapter on linear programming is particularly useful, forming as it does a very nice introduction to polyhedral combinatorics and, more generally, to the use of linear programming in combinatorics. (Even though this is widely recognized as a very important topic, most of the other accounts of this subject in book form confine themselves to network flows.) The book is generally well set out and easy to read, and the authors' style is clear and natural. It would of course be useful, perhaps essential, for anyone interested in matchings and would also serve as a good introduction to Combinatorial Optimization. I did note some minor mistakes and infelicities in my reading of it. There is some unnecessary discussion of ''applications''. (I say unnecessary because the development of the subject has not been driven by practical questions.) However the many positive features would outweigh far more grevious faults; the authors are to be congratulated on having made an important contribution to the literature.