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

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

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, December). Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy. Presented at WADS 2019, Edmonton, Canada

• Presentation Conference Type: Conference Paper (published)
• Conference Name: WADS 2019
• 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
• Print ISSN: 0302-9743
• 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