Seminário de Teoria da Computação


                       O Teorema de Grötzsch


                       Cândida Nunes da Silva

                  Sexta-feira, 10 de dezembro de 2004
                        Sala 85 (IC2), 13:00hs



                               RESUMO

O Teorema de Grötzsch, demonstrado em 1958, afirma que todo grafo
planar sem laços e sem triângulos possui uma 3-coloração de seus
vértices. Pela dualidade planar, temos também que grafos planares sem
aresta de corte e sem 3-cortes possuem uma 3-coloração de faces. 

Posteriormente, Tutte demonstrou que um grafo planar admite uma
k-coloração de faces se, e somente se, admitir um k-fluxo inteiro.
Motivado por essa equivalência entre k-coloração de faces e k-fluxos,
Tutte então propôs uma conjetura, em termos de fluxos, que estende o
Teorema de Grötzsch para grafos não necessariamente planares. Essa é a
famosa Conjetura dos 3-Fluxos de Tutte, a qual afirma que todo grafo
sem aresta de corte e sem 3-cortes admite um 3-fluxo.

A demonstração original do Teorema de Grötzsch utiliza a Fórmula de
Euler de uma forma que impossibilita sua extensão para o caso geral.
Nesta palestra apresentarei uma nova demonstração do Teorema de
Grötzsch que não depende da Fórmula de Euler, descoberta recentemente
em trabalho conjunto com Daniel Younger e Bruce Richter da University
of Waterloo. Acreditamos que esta demonstração seja um passo
importante no sentido de demonstrar a Conjetura dos 3-Fluxos de Tutte.