TY - GEN
T1 - Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
AU - Kratsch, Stefan
AU - Schweitzer, Pascal
PY - 2012
Y1 - 2012
N2 - 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, which applied to the case of two forbidden subgraphs give the following results: A dichotomy into isomorphism complete and polynomial-time solvable graph classes for all but finitely many cases, whenever neither of the forbidden graphs 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.
AB - 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, which applied to the case of two forbidden subgraphs give the following results: A dichotomy into isomorphism complete and polynomial-time solvable graph classes for all but finitely many cases, whenever neither of the forbidden graphs 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.
UR - http://www.scopus.com/inward/record.url?scp=84868021481&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-34611-8_7
DO - 10.1007/978-3-642-34611-8_7
M3 - Conference contribution
SN - 9783642346101
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 34
EP - 45
BT - Graph-Theoretic Concepts in Computer Science - 38th International Workshop, WG 2012, Revised Selcted Papers
T2 - 38th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2012
Y2 - 26 June 2012 through 28 June 2012
ER -