König-Egerváry graphs are non-Edmonds

DOI10.1007/s00373-010-0940-yzbMath1218.05143OpenAlexW2000105603MaRDI QIDQ605001

P. Mark Kayll

Publication date: 12 November 2010

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-010-0940-y

zbMATH Keywords

coveringmatchingperfect matching polytope

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Polytopes and polyhedra (52B99)

Related Items (4)

Forbidden subgraphs and the König-Egerváry property ⋮ On maximum matchings in König-Egerváry graphs ⋮ Some variants of perfect graphs related to the matching number, the vertex cover and the weakly connected domination number ⋮ Tuza's conjecture for graphs with maximum average degree less than 7

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A characterization of the graphs in which the transversal number equals the matching number
• The perfect matching polytope and solid bricks
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: König-Egerváry graphs are non-Edmonds