Graph isomorphism for graph classes characterized by two forbidden induced subgraphs

详细信息    查看全文

• 作者：Stefan Kratsch^a ; ^{stefan.kratsch@tu-berlin.de} ; Pascal Schweitzer^b ; ^{schweitzer@informatik.rwth-aachen.de}
• 关键词：Graph isomorphism ; Graph classes ; Forbidden induced subgraphs
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：216
• 期：part_P1
• 页码：240-253
• 全文大小：516 K
• 卷排序：216

文摘

We study the complexity of the Graph Isomorphism problem on graph classes that are characterized by a finite number of forbidden induced subgraphs, focusing mostly on the case of two forbidden subgraphs. We show hardness results and develop techniques for the structural analysis of such graph classes. Applied to the case of two forbidden subgraphs we obtain the following main result: A dichotomy into isomorphism complete and polynomial-time solvable graph classes for all but finitely many cases, whenever neither forbidden graph is a clique, a pan, or a complement of these graphs. Further reducing the remaining open cases we show that (with respect to graph isomorphism) forbidding a pan is equivalent to forbidding a clique of size three.