2018/07/19 by Marcelo H. de Carvalho, de Carvalho, Marcelo H., Nishad Kothari +4 · 1 citation
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1807.07339
openalex publication_date 2018/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A well-studied geometric object in combinatorial optimization is the perfect matching polytope of a graph G. In any investigation concerning the perfect matching polytope, one may assume that G is matching covered --- that is, it is a connected graph (of order at least two) and each edge lies in some perfect matching. A graph G is Birkhoff-von Neumann (BvN) if its perfect matching polytope is characterized solely by non-negativity and degree constraints. A result of Balas (1981) implies that G is BvN if and only if G does not contain a pair of vertex-disjoint odd cycles (C1,C2) such that G-V(C1)-V(C2) has a perfect matching. It follows immediately that the corresponding decision problem is in co-NP. However, it is not known to be in NP. The problem is in P if the input graph is planar --- due to a result of Carvalho, Lucchesi and Murty (2004). These authors, along with Kothari (2018), have shown that this problem is equivalent to the seemingly unrelated problem of deciding whether a given graph is C6-free. The combinatorial diameter of a polytope is the diameter of its 1-skeleton graph. A graph G is PM-compact (PMc) if the combinatorial diameter of its perfect matching polytope equals one. A result of Chvátal (1975) implies that G is PMc if and only if G does not contain a pair of vertex-disjoint even cycles (C1,C2) such that G-V(C1)-V(C2) has a perfect matching. Once again the corresponding decision problem is in co-NP, but it is not known to be in NP. The problem is in P if the input graph is bipartite or is near-bipartite --- due to a result of Wang, Lin, Carvalho, Lucchesi, Sanjith and Little (2013). In this paper, we consider the "intersection" of the aforementioned problems. We give a complete characterization of matching covered graphs that are BvN as well as PMc. (Thus the corresponding decision problem is in P.)