Speaker: |
Nishad Kothari (Univ. of Waterloo & Univ. of Vienna 200 University Ave W Waterloo, ON N2L 3G1 Canada ) |

Organiser: |
Umang Bhaskar |

Date: |
Friday, 22 Sep 2017, 16:00 to 17:00 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

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.