Graph theory seminar - Nishad Kothari

Pfaffian Bipartite Graphs

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.