Caminhos não-separadores em grafos 4-conexos

                          Orlando Lee

                 Sexta-feira, 30 de abril de 2004

                  Auditório do IC, IC-1, 13:00hs

Resumo:

Considere o seguinte problema: dado um grafo 4-conexo G e vértices u e
v em G, quando existe um caminho P em G que vai de u a v tal que G-V(P)
é 2-conexo (ou seja, o grafo obtido de G removendo-se os vértices de P é
2-conexo) ?

Este problema está relacionado com uma antiga (1975) conjectura de
Lovász. Neste seminário, mostraremos que o problema acima sempre tem
solução, exceto no caso em que G tem uma estrutura particular: "G é uma
roda dupla com centro {u,v}". 

Este é um trabalho conjunto com K. Kawarabayashi e X. Yu.