Induced minor free graphs: isomorphism and clique-width
From MaRDI portal
Publication:1702118
DOI10.1007/s00453-016-0234-8zbMath1380.05183arXiv1605.08540OpenAlexW2559777123MaRDI QIDQ1702118
Yota Otachi, Pascal Schweitzer, Rémy Belmonte
Publication date: 28 February 2018
Published in: Algorithmica, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1605.08540
Graph minors (05C83) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (3)
Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy ⋮ Graph isomorphism restricted by lists ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On graph contractions and induced minors
- Classifying the clique-width of \(H\)-free bipartite graphs
- Recent developments on graphs of bounded clique-width
- Graph isomorphism is in the low hierarchy
- The isomorphism problem for classes of graphs closed under contraction
- The complexity of induced minors and related problems
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Clique-width and edge contraction
- Approximating clique-width and branch-width
- Rank-width and vertex-minors
- Isomorphism on Subgraph-Closed Graph Classes: A Complexity Dichotomy and Intermediate Graph Classes
- Classifying the Clique-Width of H-Free Bipartite Graphs
- Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs
- Towards an Isomorphism Dichotomy for Hereditary Graph Classes
- Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
- Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
- Isomorphism for Graphs of Bounded Feedback Vertex Set Number
- Contraction Bidimensionality: The Accurate Picture
- On testing isomorphism of permutation graphs
- A Linear Time Algorithm for Deciding Interval Graph Isomorphism
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
- On the Relationship Between Clique-Width and Treewidth
- Graph isomorphism in quasipolynomial time [extended abstract]
- Structure theorem and isomorphism test for graphs with excluded topological subgraphs
- Induced minors and well-quasi-ordering
This page was built for publication: Induced minor free graphs: isomorphism and clique-width
