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

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

Título:      Sobre grafos k-críticos para o número de 
	     cruzamentos

            
Palestrante: César Israel Hernandez
             Universidad Autonoma de San Luis Potosi
             Mexico

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

Local:       auditório do NUMEC

Resumo:

O número  de cruzamentos  de um grafo  é o número  mínimo de
cruzamentos que  são necessários  para desenhar um  grafo no
plano.  Dizemos que  o grafo  é k-crítico  se seu  número de
cruzamentos é  pelo menos k e, quando  apagamos qualquer uma
de suas arestas, o número de cruzamentos do grafo resultante
é menor do que k.

Nesta palestra, vou abordar dois problemas: 

(1) existe uma família infinita de grafos k-críticos com
    grau médio 6?

(2) É possível transformar um grafo não-planar em k-crítico?