On graph contractions and induced minors

DOI10.1016/J.DAM.2010.05.005MaRDI QIDQ415282zbMATH OpenOpenAlexFDO

Authors Daniël Paulusma, Stefan Szeider, Dimitrios M. Thilikos, Pim Van 't Hof, Marcin Kamiński

Publication date 11 May 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2010.05.005

zbMATH Keywords

graph minorgraph contractiongraph induced minor

Mathematics Subject Classification ID

Graph minors (05C83)

Recommendations

• On contracting graphs to fixed pattern graphs
• Detecting fixed patterns in chordal graphs in polynomial time
• Detecting induced minors in AT-free graphs
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• The complexity of graph contractions.

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2081091 (Why is no real title available?)
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A linear time algorithm for finding tree-decompositions of small treewidth
• Contractibility and NP-completeness
• Contraction Bidimensionality: The Accurate Picture
• Contraction theorems in Hamiltonian graph theory
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XX: Wagner's conjecture
• Hierarchy of surface models and irreducible triangulations.
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Restricted Mesh Simplification Using Edge Contractions
• The complexity of induced minors and related problems
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• The computational complexity of graph contractions II: Two tough polynomially solvable cases
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(32)

• Detecting fixed patterns in chordal graphs in polynomial time
• On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
• Detecting induced star-like minors in polynomial time
• Dichotomies for tree minor containment with structural parameters
• Containment relations in split graphs
• A note on contracting claw-free graphs
• Computing pivot-minors
• Contraction obstructions for treewidth
• The complexity of contracting bipartite graphs into small cycles
• The complexity of contracting bipartite graphs into small cycles
• The reduction of graph families closed under contraction
• On contracting graphs to fixed pattern graphs
• Contracting a chordal graph to a split graph or a tree
• Contracting bipartite graphs to paths and cycles
• Induced minor models. I: Structural properties and algorithmic consequences
• Increasing the minimum degree of a graph by contractions
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• Graph editing to a fixed target
• Increasing the minimum degree of a graph by contractions
• Detecting induced minors in AT-free graphs
• The computational complexity of graph contractions II: Two tough polynomially solvable cases
• Contracting planar graphs to contractions of triangulations
• Minimal graphs for contractible and dismantlable properties
• Contracting bipartite graphs to paths and cycles
• Treewidth versus clique number. I: Graph classes with a forbidden structure
• Dichotomies for tree minor containment with structural parameters
• Contracting chordal graphs and bipartite graphs to paths and trees
• The complexity of graph contractions.
• scientific article; zbMATH DE number 4183439 (Why is no real title available?)
• 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs
• Reconfiguration of graph minors
• MSOL restricted contractibility to planar graphs

This page was built for publication: On graph contractions and induced minors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q415282)