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

a) ,

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.

—————————————————————————-

Conjecture 4 was answered by Schrijver in his 1998 paper “Counting 1-factors in Regular Bipartite Graphs” (homepages.cwi.nl/~lex/files/countpms2.ps )

@Kevin. Thanks for letting us know.

I found a nice set of slides on Chavtal’s toughness conjecture. See link below.

faculty.nps.edu/rgera/Conjectures/jmm2012/Linda-Lesniak.pdf

Very interesting conjecture that I was not aware of.

@Chandra Thanks for sharing the link.

Pingback: Walking Randomly » 90th Carnival of Mathematics