Independence numbers of graphs - an extension of the Koenig-Egervary theorem
From MaRDI portal
Publication:1256490
DOI10.1016/0012-365X(79)90066-9zbMath0404.05034MaRDI QIDQ1256490
Publication date: 1979
Published in: Discrete Mathematics (Search for Journal in Brave)
Related Items (58)
König graphs for 3-paths and 3-cycles ⋮ On some conjectures concerning critical independent sets of a graph ⋮ Combinatorial properties of the family of maximum stable 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 ⋮ Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs ⋮ WELL-COVERED GRAPHS: A SURVEY ⋮ 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 ⋮ On approximability of optimization problems related to red/blue-split graphs ⋮ A combinatorial column generation algorithm for the maximum stable set problem ⋮ On the convexity of independent set games ⋮ 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 ⋮ The price of defense ⋮ König-Egerváry graphs are non-Edmonds ⋮ On the König graphs for a 5-path and its spanning supergraphs ⋮ Critical independent sets and König-Egerváry graphs ⋮ The critical independence number and an independence decomposition ⋮ A set and collection lemma ⋮ On the parameterized vertex cover problem for graphs with perfect matching ⋮ On critical difference, independence number and matching number of graphs ⋮ Automated conjecturing. I: Fajtlowicz's Dalmatian heuristic revisited ⋮ Local maximum stable set greedoids stemming from very well-covered graphs ⋮ Forbidden subgraphs and the König-Egerváry property ⋮ On maximum matchings in König-Egerváry graphs ⋮ The complexity of König subgraph problems and above-guarantee vertex cover ⋮ On local maximum stable set greedoids ⋮ The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number ⋮ Some variants of perfect graphs related to the matching number, the vertex cover and the weakly connected domination number ⋮ Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids ⋮ A characterization of Konig-Egervary graphs using a common property of all maximum matchings ⋮ Problems on matchings and independent sets of a graph ⋮ Combinatorial and spectral properties of König-Egerváry graphs ⋮ A combinatorial algorithm for weighted stable sets in bipartite graphs ⋮ On \(\alpha\)-critical edges in König--Egerváry graphs ⋮ On König-Egerváry collections of maximum critical independent sets ⋮ Parameterizing above or below guaranteed values ⋮ On the intersection of all critical sets of a unicyclic graph ⋮ VERY WELL-COVERED GRAPHS OF GIRTH AT LEAST FOUR AND LOCAL MAXIMUM STABLE SET GREEDOIDS ⋮ König Graphs with Respect to the 4-Path and Its Spanning Supergraphs ⋮ An improved approximation for maximum \(k\)-dependent set on bipartite graphs ⋮ 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 ⋮ 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 an annihilation number conjecture ⋮ Regular graphs with equal matching number and independence number ⋮ On Duality between Local Maximum Stable Sets of a Graph and Its Line-Graph ⋮ Forbidden subgraphs and the Kőnig property ⋮ Tractability of König edge deletion problems ⋮ Ear-decompositions of matching-covered graphs ⋮ Tuza's conjecture for graphs with maximum average degree less than 7 ⋮ On partial descriptions of König graphs for odd paths and all their spanning supergraphs
Cites Work
This page was built for publication: Independence numbers of graphs - an extension of the Koenig-Egervary theorem
