Graph Isomorphism for (H₁,H₂)-free Graphs: An Almost Complete Dichotomy

DOI10.1007/S00453-020-00747-XarXiv1811.12252MaRDI QIDQ6310429FDOQ6310429

Authors: Marthe Bonamy, Nicolas Bousquet, Konrad Dabrowski, Matthew Johnson, Daniël Paulusma, Théo Pierron 

Publication date: 29 November 2018

Abstract: We resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs $H_1$ and $H_2$ for all but six pairs $(H_1,H_2)$. Schweitzer had previously shown that the number of open cases was finite, but without specifying the open cases. Grohe and Schweitzer proved that Graph Isomorphism is polynomial-time solvable on graph classes of bounded clique-width. Our work combines known results such as these with new results. By exploiting a relationship between Graph Isomorphism and clique-width, we simultaneously reduce the number of open cases for boundedness of clique-width for $(H_1,H_2)$-free graphs to five.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

This page was built for publication: Graph Isomorphism for $(H_1,H_2)$-free Graphs: An Almost Complete Dichotomy

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