Hatzel, Meike; Rabinovich, Roman; Wiederrecht, Sebastian Cyclewidth and the grid theorem for perfect matching width of bipartite graphs. (English) Zbl 07173290 Sau, Ignasi (ed.) et al., Graph-theoretic concepts in computer science. 45th international workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019. Revised papers. Cham: Springer. Lect. Notes Comput. Sci. 11789, 53-65 (2019). Summary: A connected graph \(G\) is called matching covered if every edge of \(G\) is contained in a perfect matching. Perfect matching width is a width parameter for matching covered graphs based on a branch decomposition. It was introduced by Norine and intended as a tool for the structural study of matching covered graphs, especially in the context of Pfaffian orientations. Norine conjectured that graphs of high perfect matching width contain a large grid as a matching minor, similar to the result on treewidth by Robertson and Seymour.In this paper we obtain the first results on perfect matching width since its introduction. For the restricted case of bipartite graphs, we show that perfect matching width is equivalent to directed treewidth and thus, the directed grid theorem by Kawarabayashi and Kreutzer for directed treewidth implies Norine’s conjecture.For the entire collection see [Zbl 1425.68019]. Cited in 2 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science Keywords:branch decomposition; perfect matching; directed treewidth; matching minor PDFBibTeX XMLCite \textit{M. Hatzel} et al., Lect. Notes Comput. Sci. 11789, 53--65 (2019; Zbl 07173290) Full Text: DOI arXiv