Valid Inequalities for the Maximal Matching Polytope

Given a graph G=(V,E), a subset M of E is called a matching if no two edges in M are adjacent. A matching is said to be maximal if it is not a proper subset of any other matching. The maximal matching polytope associated with graph G is the convex hull of the incidence vectors of maximal matchings in G. In this paper, we introduce new classes of valid inequalities for the maximal matching polytope.

Citation Formats
M. K. Tural, “Valid Inequalities for the Maximal Matching Polytope,” Adıyaman University Journal of Science, vol. 9, no. 2, pp. 374–385, 2019, Accessed: 00, 2020. [Online]. Available: