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

Bonamy, M.; Dabrowski, K. K.; Johnson, M.; Paulusma, D.

doi:10.1007/978-3-030-24766-9_14

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

Bonamy, M.; Dabrowski, K. K.; Johnson, M.; Paulusma, D.

Authors

M. Bonamy

K. K. Dabrowski

Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

Contributors

Zachary Friggstad
Editor

Jörg-Rüdiger Sack
Editor

Mohammad R. Salavatipour
Editor

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.

Citation

Bonamy, M., Dabrowski, K. K., Johnson, M., & Paulusma, D. (2019). Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy. In Z. Friggstad, J. Sack, & M. R. Salavatipour (Eds.), Algorithms and data structures : 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, proceedings (181-195). https://doi.org/10.1007/978-3-030-24766-9_14

Conference Name	WADS 2019
Conference Location	Edmonton, Canada
Acceptance Date	Apr 13, 2019
Online Publication Date	Jul 12, 2019
Publication Date	Jan 1, 2019
Deposit Date	May 9, 2019
Publicly Available Date	May 10, 2019
Volume	2019
Pages	181-195
Series Title	Lecture notes in computer science
Series Number	11646
Series ISSN	0302-9743,1611-3349
Book Title	Algorithms and data structures : 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, proceedings.
ISBN	9783030247652
DOI	https://doi.org/10.1007/978-3-030-24766-9_14
Public URL	https://durham-repository.worktribe.com/output/1142798

Files

Accepted Conference Proceeding (337 Kb)
PDF

Copyright 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