Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions

DOI10.1007/978-3-319-55911-7_34zbMath1485.68197OpenAlexW2601000336MaRDI QIDQ2988844

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

Mathematics Subject Classification ID

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)

Related Items (9)

Reducing the chromatic number by vertex or edge deletions ⋮ The complexity of blocking (semi)total dominating sets with edge contractions ⋮ Reducing the domination number of graphs via edge contractions and vertex deletions ⋮ Critical vertices and edges in \(H\)-free graphs ⋮ Unnamed Item ⋮ Contraction and deletion blockers for perfect graphs and \(H\)-free graphs ⋮ Blocking total dominating sets via edge contractions ⋮ Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut ⋮ Using edge contractions to reduce the semitotal domination number

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• The most vital nodes with respect to independent set and vertex cover
• Blockers for the stability number and the chromatic number
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• Maximum matchings and trees
• Combinatorial properties of the family of maximum stable sets of a graph
• 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
• Vertices Belonging to All Critical Sets of a Graph
• Hadwiger Number of Graphs with Small Chordality
• Contraction Blockers for Graphs with Forbidden Induced Paths
• Vertices Belonging to All or to No Maximum Stable Sets of a Graph
• Minimum vertex blocker clique problem

This page was built for publication: Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions