Vertex-minor reductions can simulate edge contractions

DOI10.1016/j.dam.2007.06.011zbMath1127.05097OpenAlexW2006777796MaRDI QIDQ2457014

Mamadou Moustapha Kanté

Publication date: 29 October 2007

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

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

zbMATH Keywords

tree-widthtree-decompositionrank-widthvertex-minorlocal complementationedge contractionClique-width

Mathematics Subject Classification ID

Trees (05C05) Graph minors (05C83)

Related Items

Rank-width: algorithmic and structural results, Graph Operations Characterizing Rank-Width and Balanced Graph Expressions, On the Boolean-Width of a Graph: Structure and Applications, Graph operations characterizing rank-width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Graph minors. V. Excluding a planar graph
• Graph minors. X: Obstructions to tree-decomposition
• A partial k-arboretum of graphs with bounded treewidth
• Graph minors. XIII: The disjoint paths problem
• Upper bounds to the clique width of graphs
• Approximating clique-width and branch-width
• Rank-width and vertex-minors
• Clique-width minimization is NP-hard
• On the Relationship Between Clique-Width and Treewidth
• Rank‐width is less than or equal to branch‐width
• Graph-Theoretic Concepts in Computer Science