Online talk: Meike Hatzel

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


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.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.