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 查看全文>>