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 -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)- A characterization of König-Egerváry graphs using a common property of all maximum matchings
- When is \(G^2\) a König-Egerváry graph?
- A new eigenvalue bound for independent sets
- Two more characterizations of König-Egerváry graphs
- On an annihilation number conjecture
- On König-Egerváry collections of maximum critical independent sets
- Forbidden subgraphs and the König-Egerváry property
- On some conjectures concerning critical independent sets of a graph
- Graphs with equal independence and annihilation numbers
- Critical independent sets of König-Egerváry graphs
- Critical sets, crowns and local maximum independent sets
- Automated conjecturing. I: Fajtlowicz's Dalmatian heuristic revisited
- Critical and maximum independent sets of a graph
- Some more updates on an annihilation number conjecture: pros and cons
- Computing unique maximum matchings in O(m) time for König-Egerváry graphs and unicyclic graphs
- Critical independent sets and König-Egerváry graphs
- On maximum matchings in König-Egerváry graphs
- Monotonic properties of collections of maximum independent sets of a graph
- scientific article; zbMATH DE number 4010553 (Why is no real title available?)
- New results relating independence and matchings
- Regular graphs with equal matching number and independence number
- Counterexamples to the characterisation of graphs with equal independence and annihilation number
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)
