Graph isomorphism for graph classes characterized by two forbidden induced subgraphs

DOI10.1016/j.dam.2014.10.026zbMath1350.05105OpenAlexW1967307108MaRDI QIDQ344864

Pascal Schweitzer, Stefan Kratsch

Publication date: 24 November 2016

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

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

zbMATH Keywords

forbidden induced subgraphsgraph isomorphismgraph classes

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (4)

Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy ⋮ Clique‐width: Harnessing the power of atoms ⋮ Towards an isomorphism dichotomy for hereditary graph classes ⋮ A Faster Isomorphism Test for Graphs of Small Degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A decidability result for the dominating set problem
• New graph classes of bounded clique-width
• Does co-NP have short interactive proofs ?
• Graph isomorphism is in the low hierarchy
• Complement reducible graphs
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• The isomorphism problem for classes of graphs closed under contraction
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• Two forbidden induced subgraphs and well-quasi-ordering
• Isomorphism for Graphs of Bounded Feedback Vertex Set Number
• The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• Characterizations of derived graphs

This page was built for publication: Graph isomorphism for graph classes characterized by two forbidden induced subgraphs