Even K3,3's in Bipartite Graphs

Series: 
Graph Theory Seminar
Thursday, March 28, 2013 - 12:05
1 hour (actually 50 minutes)
Location: 
Skiles 005
,  
Georgia Tech
Organizer: 
 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.