============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      Um novo resultado sobre a conjectura de 
             Thomassen

            
Palestrante: Domingos Dellamonica Jr.
             Emory University

Hora e Data: 14h, sexta-feira, 22 de outubro de 2010

Local:       auditório do NUMEC

Resumo:

A conjectura  de Thomassen afirma que para  todos os valores
de k  e g existe D  = D(k,g) suficientemente  grande tal que
todo  grafo G  com  grau médio  d(G)  >= D  deve possuir  um
subgrafo  H com  grau  médio pelo  menos  k e  cintura g  (a
cintura de um grafo é o tamanho do seu menor circuito).

Os principais resultados concretos sobre essa conjectura são
devidos a

1) Kühn e Osthus, que provaram a conjectura para g <= 6;

2) Pyber, Rödl e Szemerédi,  que provaram que a conjectura é
   verdadeira

se exigirmos  que o  grafo G tenha  grau máximo  

     Delta(G) <= exp{c  d(G)}. 

Neste seminários apresentaremos um resultado que melhora (2)
exigindo  uma   condição  mais  fraca  no   grau  máximo  de
G. (Resultado em conjunto com V. Rödl.)