In the paper An Efficient Algorithm for Graph Isomorphism 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?


1 Answer 1


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


Your Answer

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

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