Critical and maximum independent sets of a graph
From MaRDI portal
Publication:1671323
DOI10.1016/j.dam.2018.03.058zbMath1394.05089arXiv1506.00255OpenAlexW2963962341MaRDI QIDQ1671323
Adi Jarden, Eugen Mandrescu, Vadim E. Levit
Publication date: 6 September 2018
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1506.00255
Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (7)
On some conjectures concerning critical independent sets of a graph ⋮ Critical independent sets of König-Egerváry graphs ⋮ CRITICAL DUAL SET-SYSTEMS ⋮ Two more characterizations of König-Egerváry graphs ⋮ Problems on matchings and independent sets of a graph ⋮ On König-Egerváry collections of maximum critical independent sets ⋮ On an annihilation number conjecture
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Critical sets in bipartite graphs
- A set and collection lemma
- 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 the graphs in which the transversal number equals the matching number
- The critical independence number and an independence decomposition
- Graphs with equal independence and annihilation numbers
- On the intersection of all critical sets of a unicyclic graph
- Ear-decompositions of matching-covered graphs
- Independence numbers of graphs - an extension of the Koenig-Egervary theorem
- Combinatorial properties of the family of maximum stable sets of a graph
- 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
- On the structure of the minimum critical independent set of a graph
- Monotonic properties of collections of maximum independent sets of a graph
- Two more characterizations of König-Egerváry graphs
- Forbidden subgraphs and the König-Egerváry property
- On maximum matchings in König-Egerváry graphs
- Using critical sets to solve the maximum independent set problem
- Crown structures for vertex cover kernelization
- Crown reductions for the minimum weighted vertex cover problem
- Level of repair analysis and minimum cost homomorphisms of graphs
- On some conjectures concerning critical independent sets of a graph
- On the Power of Simple Reductions for the Maximum Independent Set Problem
- Vertices Belonging to All Critical Sets of a Graph
- Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
- On Finding Critical Independent and Vertex Sets
- Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
- On the core of a unicyclic graph
- A parallel algorithm for computing the critical independence number and related sets
This page was built for publication: Critical and maximum independent sets of a graph
