×

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].

MSC:

68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv