Isomorphism on subgraph-closed graph classes: a complexity dichotomy and intermediate graph classes

DOI10.1007/978-3-642-45030-3_11MaRDI QIDQ2872076zbMATH OpenOpenAlexFDO

Authors Yota Otachi, P. Schweitzer

Publication date 14 January 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-45030-3_11

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
• Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
• Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy
• Graph isomorphism for \((H_1,H_2)\)-free graphs: an almost complete dichotomy
• Towards an isomorphism dichotomy for hereditary graph classes

Cited in

(9)

• Towards an isomorphism dichotomy for hereditary graph classes
• Graph isomorphism for \((H_1,H_2)\)-free graphs: an almost complete dichotomy
• The subgraph isomorphism problem on a class of hyperedge replacement languages
• Understanding the Complexity of Induced Subgraph Isomorphisms
• Forbidden ordered subgraph vs. forbidden subgraph characterizations of graph classes
• Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
• Graph isomorphism restricted by lists
• Subgraph isomorphism on graph classes that exclude a substructure
• Subgraph isomorphism on graph classes that exclude a substructure

This page was built for publication: Isomorphism on subgraph-closed graph classes: a complexity dichotomy and intermediate graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2872076)