Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
From MaRDI portal
Publication:1784743
DOI10.1016/j.tcs.2018.06.023zbMath1400.68087arXiv1706.09052OpenAlexW2963080703WikidataQ129621989 ScholiaQ129621989MaRDI QIDQ1784743
Bernard Ries, Christophe Picouleau, Daniël Paulusma, Öznur Yaşar Diner
Publication date: 27 September 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1706.09052
Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Perfect graphs (05C17)
Related Items (12)
Using edge contractions and vertex deletions to reduce the independence number and the clique number ⋮ Assistance and interdiction problems on interval graphs ⋮ Reducing the vertex cover number via edge contractions ⋮ Reducing graph parameters by contractions and deletions ⋮ The complexity of blocking (semi)total dominating sets with edge contractions ⋮ Reducing the domination number of graphs via edge contractions and vertex deletions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Blocking total dominating sets via edge contractions ⋮ Reducing graph transversals via edge contractions ⋮ Complexity and algorithms for constant diameter augmentation problems ⋮ Using edge contractions to reduce the semitotal domination number
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimum edge blocker dominating set problem
- 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
- Supersaturation problem for color-critical graphs
- Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
- The strong perfect graph theorem
- Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
- Covering graphs with few complete bipartite subgraphs
- Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
- Paw-free graphs
- The node-deletion problem for hereditary properties is NP-complete
- Maximum matchings and trees
- Complement reducible graphs
- Combinatorial properties of the family of maximum stable sets of a graph
- Critical vertices and edges in \(H\)-free graphs
- On the number of vertices belonging to all maximum stable sets of a graph
- \(d\)-transversals of stable sets and vertex covers in weighted bipartite graphs
- Incidence matrices and interval graphs
- Reducing the chromatic number by vertex or edge deletions
- Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
- Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
- Vertices Belonging to All Critical Sets of a Graph
- Hadwiger Number of Graphs with Small Chordality
- Contraction Blockers for Graphs with Forbidden Induced Paths
- Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions
- A Linear Recognition Algorithm for Cographs
- Four classes of perfectly orderable graphs
- Vertices Belonging to All or to No Maximum Stable Sets of a Graph
- Graph Classes: A Survey
- Minimum vertex blocker clique problem
- The Pathwidth and Treewidth of Cographs
- Independent Set in P5-Free Graphs in Polynomial Time
- Obtaining a Bipartite Graph by Contracting Few Edges
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
This page was built for publication: Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
