Problemas completos no isomorfismo gráfico

Estou interessado em estudar problemas completos do isomorfismo em grafos (IG).

No artigo "Problemas polinomialmente equivalentes ao isomorfismo dos grafos", de Kellogg S. Booth, (1979), provou que muitos problemas básicos estão completos no GI usando técnicas de substituição de borda, técnicas de composição etc.

Eu gostaria de aprender mais algumas técnicas usadas em artigos recentes.

Alguém pode me sugerir alguns trabalhos recentes que estão mais concentrados em provar que alguma classe de gráfico é GI completa.

cc.complexity-theory reference-request graph-isomorphism Kumar
fonte

veja também isomorfismo gráfico da

vzn 30/09/13

O que você fez para tentar encontrar esses documentos por conta própria? Você já tentou usar métodos padrão de pesquisa de literatura (por exemplo, pesquisando no Google Scholar, encontrando todos os artigos que citam o artigo de Booth etc.)?

Respostas:

Completude do isomorfismo de gráfico para gráficos perfeitos e subclasses de gráficos perfeitos C. Boucher D. Loker (2006)

Neste artigo, provamos que o isomorfismo decisivo de gráficos de dupla divisão, a classe de gráficos exibindo uma junção de 2 e a classe de gráficos que exibem uma partição de inclinação equilibrada são GI completas. Além disso, mostramos que o problema de IG para a classe maior, incluindo essas classes de gráficos - ou seja, a classe de gráficos perfeitos - também é completo.

vzn
fonte

@gold great; saltou para mim entre as várias alternativas, em parte porque os gráficos perfeitos parecem ter muitas conexões profundas com a teoria da complexidade e possivelmente ter mais alguns grandes laços ainda não descobertos, mas "no horizonte".

vzn