Rank of maximum matchings in a graph

DOI10.1007/BF01581025zbMath0468.90052OpenAlexW1978564737MaRDI QIDQ3922477

Denis Naddef

Publication date: 1982

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01581025

zbMATH Keywords

combinatorial optimizationcyclomatic numberundirected graphcomputation of face dimensionrank of maximum matchings

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Integer programming (90C10) Duality theory (optimization) (49N15) Polytopes and polyhedra (52Bxx)

Related Items (15)

Persistency in maximum cardinality bipartite matchings ⋮ Matching structure and the matching lattice ⋮ Average connectivity and average edge-connectivity in graphs ⋮ Three-matching intersection conjecture for perfect matching polytopes of small dimensions ⋮ A superlinear bound on the number of perfect matchings in cubic bridgeless graphs ⋮ Matchings in regular graphs ⋮ Randomly colouring graphs (a combinatorial view) ⋮ An improved linear bound on the number of perfect matchings in cubic graphs ⋮ Exponentially many perfect matchings in cubic graphs ⋮ Cubic bridgeless graphs have more than a linear number of perfect matchings ⋮ Persistency in the assignment and transportation problems ⋮ Ear-decompositions of matching-covered graphs ⋮ Brick decompositions and the matching rank of graphs ⋮ Optimal ear decompositions of matching covered graphs and bases for the matching lattice ⋮ Extending matchings in graphs: A survey

Cites Work

• On certain polytopes associated with graphs
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices
• On the structure of factorizable graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Rank of maximum matchings in a graph