On graph contractions and induced minors

DOI10.1016/j.dam.2010.05.005zbMath1241.05137MaRDI QIDQ415282

Stefan Szeider, Daniël Paulusma, Dimitrios M. Thilikos, Pim van 't Hof, Marcin Kaminski

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 minor; graph contraction; graph induced minor

Mathematics Subject Classification ID

05C83: Graph minors

Related Items

Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Contracting bipartite graphs to paths and cycles, Contracting bipartite graphs to paths and cycles, Contracting chordal graphs and bipartite graphs to paths and trees, The complexity of contracting bipartite graphs into small cycles, Graph editing to a fixed target, Increasing the minimum degree of a graph by contractions, Detecting induced minors in AT-free graphs, MSOL restricted contractibility to planar graphs, Contracting planar graphs to contractions of triangulations, Containment relations in split graphs, Induced minor free graphs: isomorphism and clique-width, Detecting fixed patterns in chordal graphs in polynomial time, Contraction obstructions for treewidth, Detecting induced star-like minors in polynomial time, 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs, Increasing the Minimum Degree of a Graph by Contractions

Cites Work

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