Forbidden subgraphs and the König-Egerváry property

DOI10.1016/j.dam.2013.04.020zbMath1285.05127OpenAlexW2034045334MaRDI QIDQ2444529

Luciano N. Grippo, Martín D. Safe, Guillermo Durán, Mitre C. Dourado, Luérbio Faria, Flavia Bonomo-Braberman

Publication date: 10 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.04.020

zbMATH Keywords

maximum matchingforbidden subgraphsKönig-Egerváry graphsedge-perfect graphsKönig-Egerváry property

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Critical independent sets of König-Egerváry graphs ⋮ New results relating independence and matchings ⋮ Two more characterizations of König-Egerváry graphs ⋮ Critical and maximum independent sets of a graph ⋮ Some variants of perfect graphs related to the matching number, the vertex cover and the weakly connected domination number ⋮ On König-Egerváry collections of maximum critical independent sets ⋮ New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition ⋮ On an annihilation number conjecture ⋮ Regular graphs with equal matching number and independence number

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A characterization of the graphs in which the transversal number equals the matching number
• König-Egerváry graphs are non-Edmonds
• The critical independence number and an independence decomposition
• On local maximum stable set greedoids
• Greedoids
• The strong perfect graph theorem
• Ear-decompositions of matching-covered graphs
• Matching theory
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• König-Egerváry graphs, 2-bicritical graphs and fractional matchings
• Critical independent sets and König-Egerváry graphs
• A characterization of edge-perfect graphs and the complexity of recognizing some combinatorial optimization games
• On maximum matchings in König-Egerváry graphs
• Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
• TWO THEOREMS IN GRAPH THEORY
• Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
• Introduction to Greedoids