The critical independence number and an independence decomposition

DOI10.1016/j.ejc.2010.10.004zbMath1230.05226arXiv0912.2260OpenAlexW2067215932MaRDI QIDQ616388

Sumit K. Garg

Publication date: 7 January 2011

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0912.2260

zbMATH Keywords

König-Egerváry graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (20)

On some conjectures concerning critical independent sets of a graph ⋮ Critical independent sets of König-Egerváry graphs ⋮ Critical sets, crowns and local maximum independent sets ⋮ New results relating independence and matchings ⋮ Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs ⋮ Some more updates on an annihilation number conjecture: pros and cons ⋮ 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 ⋮ Critical independent sets and König-Egerváry graphs ⋮ Counterexamples to the characterisation of graphs with equal independence and annihilation number ⋮ Automated conjecturing. I: Fajtlowicz's Dalmatian heuristic revisited ⋮ Forbidden subgraphs and the König-Egerváry property ⋮ On maximum matchings in König-Egerváry graphs ⋮ 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 ⋮ Monotonic properties of collections of maximum independent sets of a graph ⋮ On an annihilation number conjecture ⋮ Regular graphs with equal matching number and independence number ⋮ A new eigenvalue bound for independent sets

Cites Work

• Unnamed Item
• Unnamed Item
• A characterization of the graphs in which the transversal number equals the matching number
• Matching theory
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Using critical sets to solve the maximum independent set problem
• On Finding Critical Independent and Vertex Sets
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems

This page was built for publication: The critical independence number and an independence decomposition