Blocking independent sets for H-free graphs via edge contractions and vertex deletions
DOI10.1007/978-3-319-55911-7_34zbMATH Open1485.68197OpenAlexW2601000336MaRDI QIDQ2988844FDOQ2988844
Authors: Daniël Paulusma, Bernard Ries, Christophe Picouleau 
Publication date: 19 May 2017
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-55911-7_34
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
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
- The most vital nodes with respect to independent set and vertex cover
- Minimum vertex blocker clique problem
- Blockers for the stability number and the chromatic number
- Combinatorial properties of the family of maximum stable sets of a graph
- Vertices belonging to all critical sets of a graph
- On the number of vertices belonging to all maximum stable sets of a graph
- Minimum \(d\)-blockers and \(d\)-transversals in graphs
- Vertices Belonging to All or to No Maximum Stable Sets of a Graph
- Title not available (Why is that?)
- Maximum matchings and trees
- Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
- Contraction Blockers for Graphs with Forbidden Induced Paths
Cited In (12)
- Using edge contractions to reduce the semitotal domination number
- Title not available (Why is that?)
- On blockers and transversals of maximum independent sets in co-comparability graphs
- Critical vertices and edges in \(H\)-free graphs
- Title not available (Why is that?)
- Reducing the chromatic number by vertex or edge deletions
- 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)
