Capítulo 1. Preliminares (Introdução e Notação) -
Recapitulação de resultados básicos.
Capítulo 2 - Emparelhamentos (recapitulação) : Teorema de Berge,
Teorema de Hall, Teorema de König, Teorema de Petersen.
(Parte nova): Teorema de Ore (deficiência e
empar. máximo). Teorema de Tutte (caracterização de
grafos com emparelhamentos perfeitos).
Aula 2 - 12 de agosto
Capítulo 2 - Emparelhamentos (cont.): Emparelhamentos em grafos
arbitrários: o conceito de deficiência e a a Fórmula de
Berge. Teorema de Tutte (caracterização de grafos com
emparelhamentos perfeitos).
Capítulo 2 - Emparelhamentos em grafos bipartidos
(cont.): Fórmula de Tutte-Berge. O
Teorema Estrutural de Edmonds-Gallai (enunciado).
Algoritmo de Edmonds: ideia baseada em caminhos alternantes.
Flores e botões (blossoms). Teorema sobre contração de
botões. Rotulação de vértices e construção de florestas
alternantes.
Prova de que o algoritmo de Edmonds constrói
um emparelhamento máximo.[Ver uma implementação do algoritmo
no livro Matching Theory, de Lovász and Plummer, que não faz
contração de botões.]
Notas sobre uma implementação de
Conradt-Pape (que não faz contração de botões).
Prova do Teorema da decomposição de Edmonds-Gallai (como
consequência da rotulação feita pelo
algoritmo de Edmonds).
Teorema de Thomassen: grafos planares são 5-lista-coloríveis.
Aula 12 - 23 de setembro
Capítulo 5 -Coloração de
grafos (cont.)
[Estudo em casa] Lista-aresta-coloração. Digrafos/conceito de núcleo.
Teorema de Galvin: Num grafo bipartido, o índice
cromático é igual ao índice-lista-cromático.
Existência de grafos com número cromático pelo menos k e cintura pelo menos p (Teorema
de Erdös), para quaisquer k e p dados.
Grafos perfeitos
(Teorema de Lovász).
Algumas classes de grafos perfeitos
[estudo em casa].