Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science

Profile

Publication details for Professor Matthew Johnson

Bonamy, M., Dabrowski, K.K., Johnson, M. & Paulusma, D. (2019), Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy, in Friggstad, Zachary Sack, Jörg-Rüdiger & Salavatipour, Mohammad R. eds, Lecture Notes in Computer Science 11646: WADS 2019. Edmonton, Canada, Springer, Cham, 181-195.

Author(s) from Durham

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.