Graph isomorphism for graph classes characterized by two forbidden induced subgraphs

DOI10.1016/J.DAM.2014.10.026MaRDI QIDQ344864zbMATH OpenOpenAlexFDO

Authors Stefan Kratsch, P. Schweitzer

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

graph classesgraph isomorphismforbidden induced subgraphs

Mathematics Subject Classification ID

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

Recommendations

• Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
• Logical Approaches to Computational Barriers
• Subgraph isomorphism in graph classes
• Subgraph isomorphism on graph classes that exclude a substructure
• Subgraph isomorphism on graph classes that exclude a substructure
• Graph classes characterized both by forbidden subgraphs and degree sequences
• scientific article; zbMATH DE number 3815
• On forbidden subdivision characterizations of graph classes
• Forbidden ordered subgraph vs. forbidden subgraph characterizations of graph classes
• Characterizing path graphs by forbidden induced subgraphs

Cites work

• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• A decidability result for the dominating set problem
• Characterizations of derived graphs
• Complement reducible graphs
• Does co-NP have short interactive proofs ?
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• Graph isomorphism is in the low hierarchy
• Isomorphism for graphs of bounded feedback vertex set number
• Isomorphism of graph classes related to the circular-ones property
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• New graph classes of bounded clique-width
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
• The isomorphism problem for classes of graphs closed under contraction
• Two forbidden induced subgraphs and well-quasi-ordering

Cited in

(8)

• Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy
• A Faster Isomorphism Test for Graphs of Small Degree
• Forbidden ordered subgraph vs. forbidden subgraph characterizations of graph classes
• Clique‐width: Harnessing the power of atoms
• Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
• Towards an isomorphism dichotomy for hereditary graph classes
• Isomorphism on subgraph-closed graph classes: a complexity dichotomy and intermediate graph classes
• Graph isomorphism for \((H_1,H_2)\)-free graphs: an almost complete dichotomy

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

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