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


Authors

M. Bonamy

N. Bousquet

K.K. Dabrowski

T. Pierron



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.

Citation

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. https://doi.org/10.1007/s00453-020-00747-x

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
DOI https://doi.org/10.1007/s00453-020-00747-x
Public URL https://durham-repository.worktribe.com/output/1266628

Files

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

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

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 http://creativecommons.org/licenses/by/4.0/.





You might also like



Downloadable Citations