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 Dabrowski, K.K. and Johnson, M. and Paulusma, D. (2019) 'Graph isomorphism for (H1,H2)-free graphs : an almost complete dichotomy.', in Algorithms and data structures : 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, proceedings. Cham: Springer, pp. 181-195. Lecture notes in computer science., 2019 (11646).

Abstract

We almost completely resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs H1 and H2. Schweitzer settled the complexity of this problem restricted to (H1;H2)-free graphs for all but a nite number of pairs (H1;H2), but without explicitly giving the number of open cases. Grohe and Schweitzer proved that Graph Isomorphism is polynomialtime solvable on graph classes of bounded clique-width. By combining known results with a number of new results, we reduce the number of open cases to seven. By exploiting the strong relationship between Graph Isomorphism and clique-width, we simultaneously reduce the number of open cases for boundedness of clique-width for (H1;H2)-free graphs to ve.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
(329Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1007/978-3-030-24766-9_14
Publisher statement:This is a post-peer-review, pre-copyedit version of an article published in Algorithms and data structures : 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, proceedings. The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-24766-9_14
Date accepted:13 April 2019
Date deposited:10 May 2019
Date of first online publication:12 July 2019
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar