<p>Mathon has shown that the conjecture used by Corneil and Gotlieb is false. The first reference states this fact.</p>

<p>1- P. Foggia, C.Sansone, M. Vento, A Performance Comparison of Five Algorithms for Graph Isomorphism, Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition, 2001, pp. 188-199.</p>

<p>2- R. Mathon, Sample graphs for isomorphism testing, Congressus Numerantium, 21, pp.
499-517, 1978</p>

CC BY-SA 3.0
2013-08-27T13:53:13.013Z
2013-08-27T14:06:10.230Z
2013-08-27T14:06:10.230Z
Mohammad Al-Turkistany
<p>In the paper <a href="http://scholar.google.com/scholar_url?hl=de&amp;q=http://www.seas.gwu.edu/~simhaweb/iisc/Corneil.pdf&amp;sa=X&amp;scisig=AAGBfm3Riq2QOePpaMaf4zYGqCXJrgJofQ&amp;oi=scholarr">An Efficient Algorithm for Graph Isomorphism</a> by Corneil and Gotlieb, 1970 a conjecture was stated upon which the stated algorithm relied for solving GI in polynomial time. Namely:</p>

<blockquote>
  <p>that the representative graphs exhibit the automorphism partitioning of the
  given graph</p>
</blockquote>

<p>Obviously, this conjecture isn't proven until now (otherwise we would know that GI is in P). My question is whether it was already shown to be false and possibly a counter example was given?</p>

<graph-isomorphism><automorphism>
Counterexample for Corneil's efficient algorithm for Graph Isomorphism
John D.
# Counterexample for Corneil's efficient algorithm for Graph Isomorphism

(Asked by: username_0 on 2013-08-27)

In the paper [An Efficient Algorithm for Graph Isomorphism](http://scholar.google.com/scholar_url?hl=de&q=http://www.seas.gwu.edu/~simhaweb/iisc/Corneil.pdf&sa=X&scisig=AAGBfm3Riq2QOePpaMaf4zYGqCXJrgJofQ&oi=scholarr) by Corneil and Gotlieb, 1970 a conjecture was stated upon which the stated algorithm relied for solving GI in polynomial time. Namely:

> that the representative graphs exhibit the automorphism partitioning of the
> given graph

Obviously, this conjecture isn't proven until now (otherwise we would know that GI is in P). My question is whether it was already shown to be false and possibly a counter example was given?

**Tags:** graph-isomorphism, automorphism


---

## 1 answers

### Answer by username_1 on 2013-08-27. Score: 18 | Accepted answer

Mathon has shown that the conjecture used by Corneil and Gotlieb is false. The first reference states this fact.

1- P. Foggia, C.Sansone, M. Vento, A Performance Comparison of Five Algorithms for Graph Isomorphism, Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition, 2001, pp. 188-199.

2- R. Mathon, Sample graphs for isomorphism testing, Congressus Numerantium, 21, pp.
499-517, 1978


---

