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.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ see also wikipedia graph isomorphism complete & GI-hard problems $\endgroup$
    – vzn
    Sep 30, 2013 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, 2013 at 6:43

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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, 2013 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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