Monday, November 25, 2013 4:00 pm
-
4:00 pm
EST (GMT -05:00)
Ear-decompositions of nonbipartite matching-covered graphs
Speaker: | Nishad Kothari |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics and Computer Building (MC) 5168 |
Abstract:
A connected graph is called matching-covered if each edge lies in a perfect matching. A classical result of Lovasz (1983) states that every nonbipartite matching covered graph either "contains" $K_4$, or "contains" the triangular prism (complement of a 6-cycle). Carvalho and Lucchesi (1996) gave a much simpler proof of this fundamental and very useful result. I will present their proof. I will also present an application due to Lovasz, which gives a different characterization of graphs with the Konig property (size of max. matching = size of min. vertex cover).