Polynomial time recognition of essential graphs having stability number equal to matching number

DOI10.1007/s00373-014-1483-4zbMath1321.05211OpenAlexW2099703290MaRDI QIDQ497363

Raffaele Mosca, Paolo Nobili

Publication date: 24 September 2015

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

Full work available at URL: https://doi.org/10.1007/s00373-014-1483-4

zbMATH Keywords

polynomial time algorithmmaximum matchingmaximum stable set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Two more characterizations of König-Egerváry graphs, Critical and maximum independent sets of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• A characterization of the graphs in which the transversal number equals the matching number
• Geometric algorithms and combinatorial optimization
• Testing for Equality between Maximum Matching and Minimum Node Covering
• A shy invariant of graphs
• Critical independent sets and König-Egerváry graphs
• A characterization of Konig-Egervary graphs using a common property of all maximum matchings
• Node-weighted graphs having the König-Egerváry property
• Vertices Belonging to All or to No Maximum Stable Sets of a Graph