On graph contractions and induced minors

DOI10.1016/j.dam.2010.05.005zbMath1241.05137OpenAlexW2156209401MaRDI 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 minorgraph contractiongraph induced minor

Mathematics Subject Classification ID

Graph minors (05C83)

Related Items

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

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