GI complexity dichotomy for (H₁,H₂)-free graphs
Research Question (Introduction) · arXiv:1811.12252
Status open high confidence
The source paper itself represents major progress on this research question, resolving the computational complexity of Graph Isomorphism for $(H_1,H_2)$-free graphs for all but six pairs $(H_1,H_2)$, and was published in Algorithmica in 2021. No subsequent paper resolving the remaining six open cases has been found in the indexed literature through May 2026; the complete dichotomy for all pairs $(H_1,H_2)$ remains open.
Reviewer notes. The source paper (published in Algorithmica 2021, doi:10.1007/s00453-020-00747-x) settled all but six pairs (H1,H2). Schweitzer had previously proved that only finitely many cases remain open. Wide web search (Semantic Scholar, Paulusma's publication list, arXiv) found no follow-up paper resolving the remaining six cases; the complete dichotomy question is still open with high confidence.
Context
Kratsch and Schweitzer [22] initiated the classification of Graph Isomorphism for $(H_1,H_2)$-free graphs, and Schweitzer [30] later proved that only finitely many cases remain open without specifying them. This question frames the paper's programme to complete the dichotomy.
Notes. Explicitly posed as a research question in the introduction; the paper resolves all but six pairs $(H_1,H_2)$, leaving those six as the residual open cases.
Source paper
Graph Isomorphism for $(H_1,H_2)$-free Graphs: An Almost Complete Dichotomy
Marthe Bonamy, Nicolas Bousquet, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma, Théo Pierron · 2019-09-03
https://arxiv.org/abs/1811.12252
PDF source