Skip to main content

Research Repository

Advanced Search

Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy

Bonamy, M.; Bousquet, N.; Dabrowski, K.K.; Johnson, M.; Paulusma, D.; Pierron, T.

Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy Thumbnail


M. Bonamy

N. Bousquet

K.K. Dabrowski

T. Pierron


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.


Bonamy, M., Bousquet, N., Dabrowski, K., Johnson, M., Paulusma, D., & Pierron, T. (2021). Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy. Algorithmica, 83(3), 822-852.

Journal Article Type Article
Acceptance Date Jul 7, 2020
Online Publication Date Aug 5, 2020
Publication Date 2021-03
Deposit Date Jul 10, 2020
Publicly Available Date Aug 12, 2020
Journal Algorithmica
Print ISSN 0178-4617
Electronic ISSN 1432-0541
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 83
Issue 3
Pages 822-852
Public URL


Published Journal Article (Advance online version) (2.4 Mb)

Publisher Licence URL

Copyright Statement
Advance online version This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit

You might also like

Downloadable Citations