Subgraph characterization of red/blue-split graph and kőnig egerváry graphs

DOI10.1145/1109557.1109650zbMath1192.05116OpenAlexW4238277015MaRDI QIDQ3581593

No author found.

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109650

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (29)

On some conjectures concerning critical independent sets of a graph ⋮ Note on maximal split-stable subgraphs ⋮ Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs ⋮ Stabilizing Network Bargaining Games by Blocking Players ⋮ Some more updates on an annihilation number conjecture: pros and cons ⋮ On approximability of optimization problems related to red/blue-split graphs ⋮ When is \(G^2\) a König-Egerváry graph? ⋮ Two more characterizations of König-Egerváry graphs ⋮ Critical and maximum independent sets of a graph ⋮ The price of defense ⋮ Critical independent sets and König-Egerváry graphs ⋮ On the parameterized vertex cover problem for graphs with perfect matching ⋮ Finding small stabilizers for unstable 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 ⋮ 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 ⋮ On König-Egerváry collections of maximum critical independent sets ⋮ Graph Stabilization: A Survey ⋮ Stabilizing network bargaining games by blocking players ⋮ 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 ⋮ On an annihilation number conjecture ⋮ On Duality between Local Maximum Stable Sets of a Graph and Its Line-Graph ⋮ Forbidden subgraphs and the Kőnig property

This page was built for publication: Subgraph characterization of red/blue-split graph and kőnig egerváry graphs