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).
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)
|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
|Look up in GoogleScholar|