Towards an isomorphism dichotomy for hereditary graph classes

DOI10.1007/s00224-017-9775-8zbMath1380.68232OpenAlexW1663329006MaRDI QIDQ1693994

Pascal Schweitzer

Publication date: 1 February 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/4951/

zbMATH Keywords

reductionsforbidden induced subgraphsmodular decompositiongraph isomorphismbounded color valence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (4)

Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy ⋮ Clique‐width: Harnessing the power of atoms ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
• Colouring of graphs with Ramsey-type forbidden subgraphs
• A decidability result for the dominating set problem
• A survey of the algorithmic aspects of modular decomposition
• A nonfactorial algorithm for testing isomorphism of two graphs
• Distance-hereditary graphs
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Dominating cliques in \(P_ 5\)-free graphs
• On the structure of (\(P_{5}\),\,gem)-free graphs
• List coloring in the absence of two subgraphs
• Isomorphism on Subgraph-Closed Graph Classes: A Complexity Dichotomy and Intermediate Graph Classes
• COLORED HYPERGRAPH ISOMORPHISM is fixed parameter tractable
• Towards an Isomorphism Dichotomy for Hereditary Graph Classes
• Conflict Propagation and Component Recursion for Canonical Labeling
• From Invariants to Canonization in Parallel
• Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs
• Graph isomorphism in quasipolynomial time [extended abstract]
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs

This page was built for publication: Towards an isomorphism dichotomy for hereditary graph classes