# Graph theory seminar - Nishad Kothari

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

## Pfaffian Bipartite Graphs

Speaker: Nishad Kothari University of Waterloo 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

### February 2023

S M T W T F S
29
30
31
1
4
5
7
8
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)