Graph theory seminar - Nishad Kothari
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.