Gegenbeispiel für Corneils effizienten Algorithmus für den Graphisomorphismus

In der Arbeit Ein effizienter Algorithmus für den Graphisomorphismus von Corneil und Gotlieb, 1970, wurde eine Vermutung aufgestellt, auf der der angegebene Algorithmus zur Lösung des GI in der Polynomzeit beruhte. Nämlich:

dass die repräsentativen Graphen die Automorphismus-Partitionierung des gegebenen Graphen aufweisen

Offensichtlich ist diese Vermutung bis jetzt nicht bewiesen (sonst würden wir wissen, dass GI in P ist). Meine Frage ist, ob es sich bereits als falsch erwiesen hat und möglicherweise ein Gegenbeispiel gegeben wurde?

Mathon hat gezeigt, dass die Vermutung von Corneil und Gotlieb falsch ist. Die erste Literaturstelle gibt diese Tatsache an.

1- P. Foggia, C. Sansone, M. Vento, Ein Leistungsvergleich von fünf Algorithmen für den Graphisomorphismus, Proc. 3. IAPR-TC15 Workshop Graph-based Representations in Pattern Recognition, 2001, S. 188-199.

2 - R. Mathon, Sample Graphs for Isomorphism Testing, Congressus Numerantium, 21, S. 499-517, 1978