Graph Isomorphism for (H_1,H_2)-free Graphs: An Almost Complete Dichotomy
share
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 (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 graphs to five.
READ FULL TEXT