Valiant (1979) showed that unless P = N P, 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 we refer 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 he also proved that every planar graph is Pfaffian. The complete bipartite graph $K_{3,3}$ is the smallest graph that is not Pfaffian. In general, the problem of deciding whether a given graph is Pfaffian is not known to be in N 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. It was shown by Little (1975) 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 – N P. Several years later, a structural characterization of $K_{3,3}$-free bipartite graphs was obtained by Robertson, Seymour and Thomas (1999), and independently by McCuaig (2004), and this led to a polynomial-time algorithm for deciding whether a given bipartite graph is Pfaffian.

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 (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. The talk will be mostly self-contained. I will assume only basic knowledge of graph theory. For more details, see: https://onlinelibrary.wiley.com/doi/full/10.1002/jgt.21882.

- All seminars.
- Seminars for 2019

Last updated: 05 Dec 2019