Even K3,3's in Bipartite Graphs

Graph Theory Seminar
Thursday, March 28, 2013 - 12:05
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech
 We show that any internally 4-connected non-planar bipartite graph contains a subdivision of K3,3 in which each subdivided path contains an even number of vertices. In addition to being natural, this result has broader applications in matching theory: for example, finding such a subdivision of K3,3 is the first step in an algorithm for determining whether or not a bipartite graph is Pfaffian. This is joint work with Robin Thomas.