solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看20197次
Graph Isomorphism for $(H_1,H_2)$-free Graphs: An Almost Complete Dichotomy. (arXiv:1811.12252v1 [cs.DM])
来源于:arXiv
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 查看全文>>