A characterization of Konig-Egervary graphs using a common property of all maximum matchings
From MaRDI portal
Publication:2857406
zbMath1274.05402arXiv0911.4626MaRDI QIDQ2857406
Vadim E. Levit, Eugen Mandrescu
Publication date: 1 November 2013
Full work available at URL: https://arxiv.org/abs/0911.4626
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)
Related Items (6)
Critical independent sets and König-Egerváry graphs ⋮ The maximum number of maximum dissociation sets in trees ⋮ On maximum matchings in König-Egerváry graphs ⋮ Polynomial time recognition of essential graphs having stability number equal to matching number ⋮ Combinatorial and spectral properties of König-Egerváry graphs ⋮ A characterization of König-Egerváry graphs with extendable vertex covers
Cites Work
- A characterization of the graphs in which the transversal number equals the matching number
- The critical independence number and an independence decomposition
- Ear-decompositions of matching-covered graphs
- 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
- On \(\alpha^{+}\)-stable König-Egerváry graphs
- Critical independent sets and König-Egerváry graphs
- On \(\alpha\)-critical edges in König--Egerváry graphs
- Node-weighted graphs having the König-Egerváry property
- Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
- Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
- Paths, Trees, and Flowers
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A characterization of Konig-Egervary graphs using a common property of all maximum matchings
