Blocking independent sets for H-free graphs via edge contractions and vertex deletions
From MaRDI portal
Publication:2988844
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Recommendations
- Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
- Contraction Blockers for Graphs with Forbidden Induced Paths
- Dichotomy results on the hardness of \(H\)-free edge modification problems
- Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
- Reducing the domination number of graphs via edge contractions and vertex deletions
Cites work
- scientific article; zbMATH DE number 6000604 (Why is no real title available?)
- scientific article; zbMATH DE number 3445275 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
- Blockers for the stability number and the chromatic number
- Combinatorial properties of the family of maximum stable sets of a graph
- Contraction Blockers for Graphs with Forbidden Induced Paths
- Maximum matchings and trees
- Minimum \(d\)-blockers and \(d\)-transversals in graphs
- Minimum vertex blocker clique problem
- On the number of vertices belonging to all maximum stable sets of a graph
- Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
- The most vital nodes with respect to independent set and vertex cover
- Vertices Belonging to All or to No Maximum Stable Sets of a Graph
- Vertices belonging to all critical sets of a graph
Cited in
(12)- Using edge contractions to reduce the semitotal domination number
- scientific article; zbMATH DE number 7561685 (Why is no real title available?)
- Critical vertices and edges in \(H\)-free graphs
- On blockers and transversals of maximum independent sets in co-comparability graphs
- Reducing the chromatic number by vertex or edge deletions
- scientific article; zbMATH DE number 7650254 (Why is no real title available?)
- Contraction Blockers for Graphs with Forbidden Induced Paths
- Blocking total dominating sets via edge contractions
- Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
- Reducing the domination number of graphs via edge contractions and vertex deletions
- Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut
- The complexity of blocking (semi)total dominating sets with edge contractions
This page was built for publication: Blocking independent sets for \(H\)-free graphs via edge contractions and vertex deletions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2988844)
