Ear-decompositions of nonbipartite matching-covered graphs
|Affiliation:||University of Waterloo|
|Room:||Mathematics and Computer Building (MC) 5168|
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).
200 University Avenue West
Waterloo, ON N2L 3G1