Pfaffian Orientations and Conformal Minors

Valiant (1979) showed that unless P = NP, there is no polynomial-time algorithm to compute the number of perfect matchings of a given graph --- even if the input graph is bipartite. Earlier, the physicist Kasteleyn (1963) introduced the notion of a special type of orientation of a graph, and he referred to graphs that admit such an orientation as Pfaffian graphs. Kasteleyn showed that the number of perfect matchings is easy to compute if the input graph is Pfaffian, and proved that every planar graph is Pfaffian. The smallest non-Pfaffian graph is $K_{3,3}$. In general, the problem of deciding whether a given graph is Pfaffian is not known to be in P.

Special types of minors, known as conformal minors, play a key role in the theory of Pfaffian orientations. In particular, a graph is Pfaffian if and only if each of its conformal minors is Pfaffian. Little (1975) proved that a bipartite graph G is Pfaffian if and only if G does not contain $K_{3,3}$ as a conformal minor (or, in other words, if and only if G is $K_{3,3}$-free); this places the problem of deciding whether a bipartite graph is Pfaffian in co-NP. Several years later, a structural characterization of $K_{3,3}$-free bipartite graphs was obtained by McCuaig, Robertson, Seymour and Thomas (STOC 1997), and this led to a polynomial-time algorithm for deciding whether a given bipartite graph is Pfaffian. No such algorithm is known for general graphs.

Norine and Thomas (2008) showed that, unlike the bipartite case, it is not possible to characterize all Pfaffian graphs by excluding a finite number of graphs as conformal minors. In light of everything that has been done so far, it would be interesting to even identify rich classes of Pfaffian graphs (that are nonplanar and nonbipartite).

Inspired by a theorem of Lovasz (1983), we took on the task of characterizing graphs that do not contain $K_4$ as a conformal minor --- that is, $K_4$-free graphs. In a joint work with U. S. R. Murty (Journal of Graph Theory 2016), we provided a structural characterization of planar $K_4$-free graphs. The problem of characterizing nonplanar $K_4$-free graphs is much harder, and we have evidence to believe that it is related to the problem of recognizing Pfaffian graphs. In particular, we conjecture that every graph that is $K_4$-free and $K_{3,3}$-free is also Pfaffian.