No artigo Um Algoritmo Eficiente para Isomorfismo de Gráfico de Corneil e Gotlieb, 1970, foi declarada uma conjectura sobre a qual o algoritmo declarado se baseava na resolução de IG em tempo polinomial. Nomeadamente:
que os gráficos representativos exibem a partição de automorfismo do gráfico fornecido
Obviamente, essa conjectura não está comprovada até agora (caso contrário, saberíamos que o IG está em P). Minha pergunta é se ela já foi mostrada como falsa e, possivelmente, um exemplo contrário foi dado?
fonte