Critical independent sets and König-Egerváry graphs

DOI10.1007/s00373-011-1037-yzbMath1256.05172arXiv0906.4609OpenAlexW2082717979MaRDI QIDQ1926061

Eugen Mandrescu, Vadim E. Levit

Publication date: 27 December 2012

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

Full work available at URL: https://arxiv.org/abs/0906.4609

zbMATH Keywords

coremaximum matchingmaximum independent setdeficiencycritical differencecritical 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) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (23)

Critical independent sets of König-Egerváry graphs ⋮ Critical sets, crowns and local maximum independent sets ⋮ Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs ⋮ On the critical difference of almost bipartite graphs ⋮ Hall's and Kőnig's theorem in graphs and hypergraphs ⋮ Some more updates on an annihilation number conjecture: pros and cons ⋮ When is \(G^2\) a König-Egerváry graph? ⋮ Two more characterizations of König-Egerváry graphs ⋮ Critical sets in bipartite graphs ⋮ Critical and maximum independent sets of a graph ⋮ A classification of 1-well-covered graphs ⋮ On critical difference, independence number and matching number of graphs ⋮ Forbidden subgraphs and the König-Egerváry property ⋮ On maximum matchings in König-Egerváry graphs ⋮ Polynomial time recognition of essential graphs having stability number equal to matching number ⋮ A characterization of Konig-Egervary graphs using a common property of all maximum matchings ⋮ Problems on matchings and independent sets of a graph ⋮ On König-Egerváry collections of maximum critical independent sets ⋮ On the König deficiency of zero-reducible graphs ⋮ 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

Cites Work

• A characterization of the graphs in which the transversal number equals the matching number
• The critical independence number and an independence decomposition
• Matching theory
• 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
• Combinatorial properties of the family of maximum stable sets of a graph
• König-Egerváry graphs, 2-bicritical graphs and fractional matchings
• A new greedoid: The family of local maximum stable sets of a forest
• On \(\alpha^{+}\)-stable König-Egerváry graphs
• Using critical sets to solve the maximum independent set problem
• On \(\alpha\)-critical edges in 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
• Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
• Vertex packings: Structural properties and algorithms
• On Finding Critical Independent and Vertex Sets
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• Unnamed Item

This page was built for publication: Critical independent sets and König-Egerváry graphs