On maximum matchings in König-Egerváry graphs

DOI10.1016/j.dam.2013.01.005zbMath1287.05119OpenAlexW2008490379MaRDI QIDQ2446347

Vadim E. Levit, Eugen Mandrescu

Publication date: 16 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.01.005

zbMATH Keywords

maximum matchingmaximum independent set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

On some conjectures concerning critical independent sets of a graph, On graphs admitting two disjoint maximum independent sets, Critical independent sets of König-Egerváry graphs, Critical sets, crowns and local maximum independent sets, New results relating independence and matchings, Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs, Some more updates on an annihilation number conjecture: pros and cons, Two more characterizations of König-Egerváry graphs, Critical and maximum independent sets of a graph, Forbidden subgraphs and the König-Egerváry property, Crowns in bipartite graphs, Combinatorial and spectral properties of König-Egerváry graphs, On König-Egerváry collections of maximum critical independent sets, On the intersection of all critical sets of a unicyclic graph, New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition, Monotonic properties of collections of maximum independent sets of a graph, On an annihilation number conjecture, Regular graphs with equal matching number and independence number

Cites Work

• 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
• Ear-decompositions of matching-covered graphs
• Matching theory
• Testing for Equality between Maximum Matching and Minimum Node Covering
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios
• König-Egerváry graphs, 2-bicritical graphs and fractional matchings
• On the number of vertices belonging to all maximum stable sets of a graph
• On \(\alpha^{+}\)-stable König-Egerváry graphs
• Critical independent sets and König-Egerváry graphs
• Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
• On \(\alpha\)-critical edges in König--Egerváry graphs
• Forbidden subgraphs and the Kőnig property
• A characterization of Konig-Egervary graphs using a common property of all maximum matchings
• Node-weighted graphs having the König-Egerváry property
• Subgraph characterization of red/blue-split graph and kőnig egerváry graphs