Monday, November 25, 2013 — 4:00 PM EST

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).

Location 
MC - Mathematics & Computer Building
5168
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
  1. 2019 (143)
    1. October (14)
    2. September (15)
    3. August (9)
    4. July (17)
    5. June (18)
    6. May (16)
    7. April (9)
    8. March (24)
    9. February (13)
    10. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)