Seminário de Teoria da Computação


                     Problemas de partição em grafos


		              Simone Dantas

                  Quinta-feira, 25 de novembro de 2004
		  ^^^^^^^^^^^^^ <--- NOTEM MUDANÇA DE DIA
                        Auditório (IC1), 13:00hs



                               RESUMO

Neste seminario serao apresentados problemas de particao em grafos,
suas caracterizacoes, algoritmos e classificacoes segundo a
complexidade computacional.  Inicialmente, consideramos uma
generalizacao do problema de coloracao classica: o problema de
coloracao por listas.  Apresentaremos a caracterizacao dos grafos que
satisfazem a igualdade na versao coloracao por listas do teorema de
Nordhaus-Gaddum. Em seguida, apresentamos a complexidade do problema
Grafo Sanduiche (k,l). Finalmente, estudamos o conceito de H-particao
e analisamos todos os problemas de particao de vertices em quatro
partes nao-vazias com somente restricoes externas de acordo com a
estrutura de um grafo modelo H. Alem disso, apresentamos outros
problemas solucionados a partir deste estudo.