The critical independence number and an independence decomposition
From MaRDI portal
(Redirected from Publication:616388)
Abstract: An independent set is a extit{critical independent set} if , for any independent set . The extit{critical independence number} of a graph is the cardinality of a maximum critical independent set. This number is a lower bound for the independence number and can be computed in polynomial-time. Any graph can be decomposed into two subgraphs where the independence number of one subgraph equals its critical independence number, where the critical independence number of the other subgraph is zero, and where the sum of the independence numbers of the subgraphs is the independence number of the graph. A proof of a conjecture of Graffiti.pc yields a new characterization of K"{o}nig-Egervary graphs: these are exactly the graphs whose independence and critical independence numbers are equal.
Recommendations
- A generalization of the independence number
- Bounds for the Independence Number of Critical Graphs
- scientific article; zbMATH DE number 866059
- On the independence number of random graphs
- Approximating the minimum maximal independence number
- Approximating the independence number via the \(\vartheta\)-function
- A note on critical independence reductions
- Independence number, connectivity and \((a,b,k)\)-critical graphs
- Independence number of hypergraphs under degree conditions
- Publication:4735212
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A characterization of the graphs in which the transversal number equals the matching number
- A note on critical independence reductions
- Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
- Independence numbers of graphs - an extension of the Koenig-Egervary theorem
- Matching theory
- On Finding Critical Independent and Vertex Sets
- Using critical sets to solve the maximum independent set problem
Cited in
(22)- Critical independent sets and König-Egerváry graphs
- New results relating independence and matchings
- On maximum matchings in König-Egerváry graphs
- Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs
- Forbidden subgraphs and the König-Egerváry property
- Monotonic properties of collections of maximum independent sets of a graph
- On an annihilation number conjecture
- scientific article; zbMATH DE number 4010553 (Why is no real title available?)
- A new eigenvalue bound for independent sets
- On some conjectures concerning critical independent sets of a graph
- Counterexamples to the characterisation of graphs with equal independence and annihilation number
- When is \(G^2\) a König-Egerváry graph?
- Automated conjecturing. I: Fajtlowicz's Dalmatian heuristic revisited
- Two more characterizations of König-Egerváry graphs
- On König-Egerváry collections of maximum critical independent sets
- Critical independent sets of König-Egerváry graphs
- A characterization of König-Egerváry graphs using a common property of all maximum matchings
- Graphs with equal independence and annihilation numbers
- Critical and maximum independent sets of a graph
- Critical sets, crowns and local maximum independent sets
- Regular graphs with equal matching number and independence number
- Some more updates on an annihilation number conjecture: pros and cons
This page was built for publication: The critical independence number and an independence decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616388)
