Matching minors are a specialisation of minors fit for the study of graph with perfect matchings. The notion of matching minors has been used to give a structural description of bipartite graphs on which the number of perfect matchings can becomputed efficiently, based on a result of Little, by McCuaig et al. in 1999.In this paper we generalise basic ideas from the graph minor series by Robertson and Seymour to the setting of bipartite graphs with perfect matchings. We introducea version of Erdos-Posa property for matching minors and find a direct link between this property and planarity. From this, it follows that a class of bipartite graphs withperfect matchings has bounded perfect matching width if and only if it excludes aplanar matching minor. We also present algorithms for bipartite graphs of bounded perfect matching width for a matching version of the disjoint paths problem, matching minor containment, and for counting the number of perfect matchings. From our structural results, we obtain that recognising whether a bipartite graphGcontains afixed planar graphHas a matching minor, and that counting the number of perfect matchings of a bipartite graph that excludes a fixed planar graph as a matching minor are both polynomial time solvable.
翻译:匹配未成年人是适合使用完美匹配的图形的未成年人的一种特殊特征。 匹配未成年人的概念被用于对双边图形进行结构性描述, 其上根据1999年由McCuaig等人(Little)和McCuaig等人(McCuaig等人)得出的结果, 能够有效地对完美匹配的数量进行匹配。 在本文中, 我们把由Robertson和Seymour( Robertson and Seymour) 绘制的图小系列中的基本想法概括到有完美匹配的双边图形的设置。 我们为匹配未成年人和找到此属性与计划之间的直接联系。 从结构结果中, 我们了解到, 有完美匹配的双方图形Gcontains( perperfects) 相匹配的双边图形将完美匹配宽度捆绑在一起, 只要它排除一个平面图的最小匹配比例图, 我们也会为匹配的双面平面图表的匹配数字。