Contraction Blockers for Graphs with Forbidden Induced Paths
From MaRDI portal
Recommendations
- Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
- Forbidden induced subgraph characterization of cograph contractions
- Contraction obstructions for connected graph searching
- scientific article; zbMATH DE number 7650254
- Blocking independent sets for \(H\)-free graphs via edge contractions and vertex deletions
- Contractible edges in \(k\)-connected graphs with some forbidden subgraphs
- Blocking total dominating sets via edge contractions
- Contracting few edges to remove forbidden induced subgraphs
- Characterizing path graphs by forbidden induced subgraphs
- Forbidding and enforcing on graphs
Cites work
- A Linear Recognition Algorithm for Cographs
- 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
- Complement reducible graphs
- Complexity of most vital nodes for independent set in graphs related to tree structures
- Four classes of perfectly orderable graphs
- Graph Classes: A Survey
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3632548 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- Incidence matrices and interval graphs
- Independent set in P₅-free graphs in polynomial time
- Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
- Minimum \(d\)-blockers and \(d\)-transversals in graphs
- Minimum vertex blocker clique problem
- Obtaining a bipartite graph by contracting few edges
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- On the NP-hardness of edge-deletion and -contraction problems
- On the removal of forbidden graphs by edge-deletion or by edge- contraction
- Parameterized complexity of three edge contraction problems with degree constraints
- The most vital nodes with respect to independent set and vertex cover
- The Pathwidth and Treewidth of Cographs
Cited in
(18)- Critical vertices and edges in \(H\)-free graphs
- Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
- Blocking total dominating sets via edge contractions
- Using edge contractions to reduce the semitotal domination number
- 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
- Reducing the chromatic number by vertex or edge deletions
- The complexity of blocking (semi)total dominating sets with edge contractions
- Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
- Contracting few edges to remove forbidden induced subgraphs
- Blocking independent sets for \(H\)-free graphs via edge contractions and vertex deletions
- A good characterization of cograph contractions
- Forbidden induced subgraph characterization of cograph contractions
- Reducing the domination number of graphs via edge contractions
- Split contraction: the untold story
- Obtaining split graphs by edge contraction
- scientific article; zbMATH DE number 7650254 (Why is no real title available?)
- Obtaining split graphs by edge contraction
This page was built for publication: Contraction Blockers for Graphs with Forbidden Induced Paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947020)
