2019/02/04 by Meike Hatzel, Hatzel, Meike, Roman Rabinovich +3 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1902.01322
A connected graph G is called matching covered if every edge of G is\ncontained in a perfect matching. Perfect matching width is a width parameter\nfor matching covered graphs based on a branch decomposition. It was introduced\nby Norine and intended as a tool for the structural study of matching covered\ngraphs, especially in the context of Pfaffian orientations. Norine conjectured\nthat graphs of high perfect matching width would contain a large grid as a\nmatching minor, similar to the result on treewidth by Robertson and Seymour. In\nthis paper we obtain the first results on perfect matching width since its\nintroduction. For the restricted case of bipartite graphs, we show that perfect\nmatching width is equivalent to directed treewidth and thus the Directed Grid\nTheorem by Kawarabayashi and Kreutzer for directed treewidth implies Norine's\nconjecture.\n