<ul>
<li><a href="https://cs.uwaterloo.ca/~dloker/papers/CS-2006-32.pdf" rel="nofollow">Graph Isomorphism Completeness for Perfect Graphs
and Subclasses of Perfect Graphs</a>
C. Boucher D. Loker (2006)</li>
</ul>

<blockquote>
  <p>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.</p>
</blockquote>

CC BY-SA 3.0
2013-10-01T15:07:59.743Z
@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.
vzn
CC BY-SA 3.0
2013-09-30T15:57:00.397Z
2013-09-30T15:57:00.397Z
vzn
<p>I am interested to study Graph Isomorphism (GI) complete problems.</p>

<p>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. </p>

<p>I would like to learn some more techniques which are used in recent papers.</p>

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

CC BY-SA 3.0
2013-09-30T00:34:48.383Z
see also wikipedia [graph isomorphism complete & GI-hard problems](http://en.wikipedia.org/wiki/Graph_isomorphism_problem#GI-complete_and_GI-hard_problems)
vzn
CC BY-SA 3.0
2013-09-30T06:43:27.163Z
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.)?
D.W.
<cc.complexity-theory><reference-request><graph-isomorphism>
On Graph Isomorphism Complete Problems
Kumar
# On Graph Isomorphism Complete Problems

(Asked by: username_0 on 2013-09-29)

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.

**Tags:** cc.complexity-theory, reference-request, graph-isomorphism
> **Comments:**
> **username_1**: see also wikipedia [graph isomorphism complete & GI-hard problems](http://en.wikipedia.org/wiki/Graph_isomorphism_problem#GI-complete_and_GI-hard_problems)  
> **username_2**: 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.)?  

---

## 1 answers

### Answer by username_1 on 2013-09-30. Score: 4 | Accepted answer

* [Graph Isomorphism Completeness for Perfect Graphs
  and Subclasses of Perfect Graphs](https://cs.uwaterloo.ca/~dloker/papers/CS-2006-32.pdf)
  C. Boucher D. Loker (2006)

> 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.

> **Comments:**
> **username_1**: @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.  

---

