Contraindo Arestas em Grafos 3-Conexos

Palestrante: João Paulo Costalonga, UFES.

Data: 19 de outubro de 2015, 15h

Local: Campus Gragoatá, Bloco H, Sala 401

Resumo: Uma aresta e em um grafo 3-conexo G é dita contratível se G/e é 3-conexo e H-contratível se G/e é 3-conexo com um menor isomorfo a H. Arestas com essas propriedades são importantes para demonstrações por indução. São conhecidas cotas inferiores ótimas para o número de arestas contratíveis em um grafo 3-conexo G em função de |G|. Também é conhecida a existência de arestas H contratíveis se G possui um menor isomorfo a H com |H|>|G|. Em nosso mais recente trabalho, introduzimos uma cota inferior ótima para o número de arestas H-contratíveis em função de |G|-|H|. Além disso, demonstramos que essas arestas podem ser escolhidas em uma floresta de G.