Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Graph Isomorphism for (H1,H2)-free graphs: An Almost Complete Dichotomy

Bonamy, M. and Bousquet, N. and Dabrowski, K.K. and Johnson, M. and Paulusma, D. and Pierron, T. (2021) 'Graph Isomorphism for (H1,H2)-free graphs: An Almost Complete Dichotomy.', Algorithmica., 83 (3). pp. 822-852.

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.

Item Type:Article
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
(486Kb)
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF (Advance online version)
(2320Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1007/s00453-020-00747-x
Publisher statement: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/.
Date accepted:07 July 2020
Date deposited:14 July 2020
Date of first online publication:05 August 2020
Date first made open access:12 August 2020

Save or Share this output

Export:
Export
Look up in GoogleScholar