Springer, Algorithmica, 3(83), p. 822-852, 2020
DOI: 10.1007/s00453-020-00747-x
Full text: Download
AbstractWe resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs $ H_{1} $ H 1 and $H_2$ H 2 for all but six pairs $(H_1,H_2)$ ( H 1 , H 2 ) . Schweitzer had previously shown that the number of open cases was finite, but without specifying the open cases. Grohe and Schweitzer proved that Graph Isomorphism is polynomial-time solvable on graph classes of bounded clique-width. Our work combines known results such as these with new results. By exploiting a relationship between Graph Isomorphism and clique-width, we simultaneously reduce the number of open cases for boundedness of clique-width for $(H_1,H_2)$ ( H 1 , H 2 ) -free graphs to five.