Excluding a planar matching minor in bipartite graphs

DOI10.1016/J.JCTB.2023.09.003MaRDI QIDQ6144397zbMATH OpenOpenAlexFDO

Authors Archontia C. Giannopoulou, Stephan Kreutzer, Sebastian Wiederrecht

Publication date 29 January 2024

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.00703

zbMATH Keywords

butterfly minorcounting perfect matchingsdigraphsdisjoint pathsErdős-Pósa propertymatching minorperfect matching

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

Abstract: 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.

Recommendations

• Matching minors in bipartite graphs
• Maximum matching in graphs with an excluded minor
• Cyclewidth and the grid theorem for perfect matching width of bipartite graphs
• On the number of perfect matchings in a bipartite graph

Cites work

• A characterization of convertible (0,1)-matrices
• Adapting the directed grid theorem into an FPT algorithm
• Bipartite graphs with a perfect matching and digraphs
• Characterization of even directed graphs
• Classes of directed graphs
• Coverings of Bipartite Graphs
• Cyclewidth and the grid theorem for perfect matching width of bipartite graphs
• Digraphs of directed treewidth one
• Directed tree-width
• Even dicycles
• Generating bricks
• Graph Drawing
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. V. Excluding a planar graph
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XVI: Excluding a non-planar graph
• Graph minors. XX: Wagner's conjecture
• scientific article; zbMATH DE number 3149610 (Why is no real title available?)
• scientific article; zbMATH DE number 1156577 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• Matching theory
• On n-extendable graphs
• Packing directed circuits exactly
• Paths, Trees, and Flowers
• Permanents, Pfaffian orientations, and even directed circuits
• Pólya's permanent problem
• S-functions for graphs
• The Directed Flat Wall Theorem
• The directed grid theorem
• The embeddings of a graph—A survey
• The point-set embeddability problem for plane graphs
• Two Algorithms for Bipartite Graphs
• Über eine Eigenschaft der ebenen Komplexe

Cited in

(5)

• Cyclewidth and the grid theorem for perfect matching width of bipartite graphs
• A matching-minor monotone parameter for bipartite graphs
• Matching minors in bipartite graphs
• Killing a vortex
• Hitting cycles through prescribed vertices or edges

This page was built for publication: Excluding a planar matching minor in bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6144397)