On graph contractions and induced minors

DOI10.1016/J.DAM.2010.05.005zbMATH Open1241.05137OpenAlexW2156209401MaRDI QIDQ415282FDOQ415282

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

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

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.

zbMATH Keywords

graph minorgraph contractiongraph induced minor

Mathematics Subject Classification ID

Graph minors (05C83)

Cites Work

• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• Title not available (Why is that?)
• Graph minors. XX: Wagner's conjecture
• Graph minors. XIII: The disjoint paths problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Title not available (Why is that?)
• A linear time algorithm for finding tree-decompositions of small treewidth
• Contraction Bidimensionality: The Accurate Picture
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• 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
• Contractibility and NP-completeness
• Contraction theorems in Hamiltonian graph theory
• Hierarchy of surface models and irreducible triangulations.
• Restricted Mesh Simplification Using Edge Contractions
• Title not available (Why is that?)

Cited In (23)

• 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
• Increasing the Minimum Degree of a Graph by Contractions
• Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
• Containment relations in split graphs
• Contraction obstructions for treewidth
• The complexity of contracting bipartite graphs into small cycles
• The reduction of graph families closed under contraction
• Contracting bipartite graphs to paths and cycles
• 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
• Graph editing to a fixed target
• Increasing the minimum degree of a graph by contractions
• Detecting induced minors in AT-free graphs
• Minimal graphs for contractible and dismantlable properties
• Contracting planar graphs to contractions of triangulations
• Contracting bipartite graphs to paths and cycles
• Contracting chordal graphs and bipartite graphs to paths and trees
• Title not available (Why is that?)
• 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs
• Induced minor free graphs: isomorphism and clique-width
• 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)