solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看22107次
Cyclewidth and the Grid Theorem for Perfect Matching Width of Bipartite Graphs. (arXiv:1902.01322v2 [math.CO] UPDATED)
来源于:arXiv
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 would 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. 查看全文>>