M. Bonamy
Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy
Bonamy, M.; Dabrowski, K. K.; Johnson, M.; Paulusma, D.
Authors
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
You might also like
Solving Infinite-Domain CSPs Using the Patchwork Property
(2023)
Conference Proceeding
Disjunctive Temporal Problems under Structural Restrictions
(2021)
Conference Proceeding
Fine-Grained Complexity of Temporal Problems
(2020)
Conference Proceeding
Independent transversals versus transversals
(2019)
Conference Proceeding
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search