11
$\begingroup$

I am interested to study Graph Isomorphism (GI) complete problems.

In the Paper " Problems Polynomially Equivalent to Graph Isomorphism" by Kellogg S. Booth, (1979), proved that many basic problems are GI complete by using Edge replacement techniques, Composition techniques etc.

I would like to learn some more techniques which are used in recent papers.

Can some one suggest me some recent papers which are more concentrated in proving some graph class is GI complete.

$\endgroup$
  • 4
    $\begingroup$ see also wikipedia graph isomorphism complete & GI-hard problems $\endgroup$ – vzn Sep 30 '13 at 0:34
  • 2
    $\begingroup$ What have you done, to try to find such papers on your own? Have you tried using standard literature search methods (e.g., searching on Google Scholar, finding all papers that cite the Booth paper, etc.)? $\endgroup$ – D.W. Sep 30 '13 at 6:43
4
$\begingroup$

In this paper, we prove that deciding isomorphism of double split graphs, the class of graphs exhibiting a 2-join, and the class of graphs exhibiting a balanced skew partition are GI-complete. Further, we show that the GI problem for the larger class including these graph classes–that is, the class of perfect graphs–is also GI-complete.

$\endgroup$
  • $\begingroup$ @gold great; it jumped out at me among the various alternatives partly because perfect graphs seem to have many deep connections to complexity theory & seem possibly to have some further large not-yet-discovered but "on the horizon" ties. $\endgroup$ – vzn Oct 1 '13 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.