Towards an Isomorphism Dichotomy for Hereditary Graph Classes

摘要: In this paper we resolve the complexity of isomorphism problem on all but finitely many graph classes characterized by two forbidden induced subgraphs. To end develop new techniques applicable for structural and algorithmic analysis graphs. First, a methodology to show completeness providing general framework unifying various reduction techniques. Second, generalize concept modular decomposition colored graphs, allowing non-standard decompositions. We that, given suitable functor, reduces checking prime Third, extend bounded color valence hypergraph hypergraphs class size as follows. say has generalized at most k if, after removing vertices in k, each C every vertex neighbors or non-neighbors C. that graphs can be solved polynomial time.