Graph theory seminar - Nishad KothariExport this event to calendar

Wednesday, July 16, 2014 — 3:30 PM EDT

Pfaffian Bipartite Graphs

Speaker: Nishad Kothari
Affiliation: University of Waterloo
Room: Mathematics 3 (M3) 2134

Abstract:  

A graph is Pfaffian if it admits a Pfaffian orientation. Little (1975) showed that a bipartite graph is Pfaffian if and only if it does not "contain" $K_{3,3}$. This implies that the problem of deciding whether a bipartite graph is Pfaffian is in co-NP. Around 1999, Robertson, Seymour and Thomas, and independently McCuaig, showed that, for bipartite graphs, this problem is in P (i.e. poly-time solvable).

I will sketch a proof of Little's theorem given by Carvalho, Lucchesi and Murty. Towards the end, I will discuss how our on-going work has connections to Pfaffian orientations.

Location 
M3 - Mathematics 3
2134
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
31
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
1
2
3
4
  1. 2023 (13)
    1. February (5)
    2. January (8)
  2. 2022 (150)
    1. December (8)
    2. November (18)
    3. October (15)
    4. September (11)
    5. August (2)
    6. July (17)
    7. June (17)
    8. May (10)
    9. April (12)
    10. March (18)
    11. February (10)
    12. January (13)
  3. 2021 (103)
  4. 2020 (119)
  5. 2019 (167)
  6. 2018 (136)
  7. 2017 (103)
  8. 2016 (137)
  9. 2015 (136)
  10. 2014 (88)
  11. 2013 (48)
  12. 2012 (39)
  13. 2011 (36)
  14. 2010 (40)
  15. 2009 (40)
  16. 2008 (39)
  17. 2007 (15)