## Graph Isomorphism for \$(H_1,H_2)\$-free Graphs: An Almost Complete Dichotomy. (arXiv:1811.12252v1 [cs.DM])

We consider the Graph Isomorphism problem for classes of graphs characterized by two forbidden induced subgraphs \$H_1\$ and \$H_2\$. By combining old and new results, Schweitzer settled the computational complexity of this problem restricted to \$(H_1,H_2)\$-free graphs for all but a finite number of pairs \$(H_1,H_2)\$, but without explicitly giving the number of open cases. Grohe and Schweitzer proved that Graph Isomorphism is polynomial-time solvable on graph classes of bounded clique-width. By combining previously known results for Graph Isomorphism with known results for boundedness of clique-width, we reduce the number of open cases to 14. By proving a number of new results we then further reduce this number to seven. By exploiting the strong relationship between Graph Isomorphism and clique-width, we also prove that the class of \$(\mbox{gem},P_1+2P_2)\$-free graphs has unbounded clique-width. This reduces the number of open cases for boundedness of clique-width for \$(H_1,H_2)\$-free grap查看全文

## Solidot 文章翻译

 你的名字 留空匿名提交 你的Email或网站 用户可以联系你 标题 简单描述 内容 We consider the Graph Isomorphism problem for classes of graphs characterized by two forbidden induced subgraphs \$H_1\$ and \$H_2\$. By combining old and new results, Schweitzer settled the computational complexity of this problem restricted to \$(H_1,H_2)\$-free graphs for all but a finite number of pairs \$(H_1,H_2)\$, but without explicitly giving the number of open cases. Grohe and Schweitzer proved that Graph Isomorphism is polynomial-time solvable on graph classes of bounded clique-width. By combining previously known results for Graph Isomorphism with known results for boundedness of clique-width, we reduce the number of open cases to 14. By proving a number of new results we then further reduce this number to seven. By exploiting the strong relationship between Graph Isomorphism and clique-width, we also prove that the class of \$(\mbox{gem},P_1+2P_2)\$-free graphs has unbounded clique-width. This reduces the number of open cases for boundedness of clique-width for \$(H_1,H_2)\$-free grap