Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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
