I always have exactly one bed-time mathematical book to read (for an hour) before going to sleep. It helps me learn new concepts and hopefully stumble upon interesting open problems. Matching Theory by Laszlo Lovasz and Michael D. Plummer has been my bed-time book for the last six months. I bought this book 3 years back (during my PhD days) but never got a chance to read it. This book often disappears from Amazon’s stock. I guess they are printing it on-demand.
If you are interested in learning the algorithmic and combinatorial foundations of Matching Theory (with a historic perspective), then this book is a must read. Today’s post is about the open problems mentioned in Matching Theory book. If you know the status (or progress) of these problems, please leave a comment.
1 . Consistent Labeling and Maximum Flow
Conjecture (Fulkerson) : Any consistent labelling procedure results in a maximum flow in polynomial number of steps.
2. Toughness and Hamiltonicity
The toughness of a graph , is defined to be , if and to be , if . Here is the number of components of .
Conjecture (Chvatal 1973) : There exists a positive real number such that for every graph , implies is Hamiltonian.
3. Perfect Matchings and Bipartite Graphs
Theorem : Let be a set, and suppose that for . Let be a bipartite graph such that
b) has a perfect matching , and
c) if any edge of is deleted, property (b) fails to hold in the resulting graph.
Then, the number of vertices in with degree is at most .
Conjecture : The conclusion of the above theorem holds for non-bipartite graphs as well.
4. Number of Perfect Matchings
Conjecture (Schrijver and W.G.Valiant 1980) : Let denote the minimum number of perfect matchings a k-regular bipartite graph on 2n points can have. Then, .
5. Elementary Graphs
Conjecture : For there exist constants and such that every k-regular elementary graph on 2n vertices, without forbidden edges , contains at least perfect matchings. Furthermore as .
6. Number of colorations
Conjecture (Schrijver’83) : Let G be a k-regular bipartite graph on 2n vertices. Then the number of colorings of the edges of G with k given colors is at least .
7. The Strong Perfect Graph Conjecture (resolved)
Theorem : A graph is perfect if and only if it does not contain, as an induced subgraph, an odd hole or an odd antihole.