Monday, February 1, 3pm ET (8pm GMT, 9am Tue NZDT)
Meike Hatzel, TU Berlin
Perfect Matching Width and a grid minor theorem for bipartite graphs

Abstract:

The grid theorem stating that a graph has small treewidth if and only if it contains no large grid as a minor is known to be an important step in the work by Robertson and Seymour leading to the graph structure theorem. Norine conjectured that a similar property holds on graphs in which every edge is contained in a perfect matching for a bipartite grid version and a width parameter called Perfect matching width. This talk presents a partial solution to this conjecture. We prove a grid theorem using perfect matching width on bipartite graphs by showing that it is equivalent to the directed treewidth and thus we can transfer the directed grid theorem by Kawarabayashi and Kreutzer.