On maximum matchings in König-Egerváry graphs
From MaRDI portal
Publication:2446347
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
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
