Graph isomorphism for graph classes characterized by two forbidden induced subgraphs

DOI10.1016/J.DAM.2014.10.026zbMATH Open1350.05105OpenAlexW1967307108MaRDI QIDQ344864FDOQ344864

P. 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

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

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)

Cites Work

• Complement reducible graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Title not available (Why is that?)
• Characterizations of derived graphs
• Title not available (Why is that?)
• Does co-NP have short interactive proofs ?
• New graph classes of bounded clique-width
• 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
• Isomorphism for Graphs of Bounded Feedback Vertex Set Number
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• Graph isomorphism is in the low hierarchy
• Two forbidden induced subgraphs and well-quasi-ordering
• The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
• A decidability result for the dominating set problem
• Title not available (Why is that?)

Cited In (5)

• 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
• Towards an isomorphism dichotomy for hereditary graph classes

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)