Sobre grafos perfeitos

Orientador : Claudio L. LucchesiDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da ComputaçãoResumo: O primeiro capítulo introduz a noção de grafos perfeitos e as antigas conjeturas de Berge. A primeira delas, demontrada por Lovász, consta do capítulo 1 com o nome de Teorema dos Grafos Perfeitos. O segundo capítulo apresenta propriedades fundamentais dos grafos críticos (i. é, imperfeitos minimais) e os chamados grafos particionáveis. O capítulo termina com a apresentação dos grafos de cliques máximos de Tucker. O terceiro e último capítulo apresenta uma variada coleção de classes de grafos perfeitos. Foi consegui da uma tênue unificação de algumas dessas classes. O apêndice considera a segunda conjetura, a chamada conjetura "forte", e apresenta um resumo de algumas classes para as quais a conjetura valeAbstract: The first chapter introduces the notion of perfect graphs and Berge's old conjecture, proved by Lovász, appears in chapter 1 under the name or Perfect Graphs Theorem. The second chapter presents fundamental properties of critical graphs (i. e., minimal imperfect graphs) and the so-called partitionable graphs. The chapter concludes with a presentation of Tucker's maximum clique graphs. The third and the last chapter presents a broad colection or classes of perfect graphs. The chapter presents a weak unification or these classes. The appendix analyzes the second conjecture, the so-called "strong" conjecture, and presents a survey of some classes over which this conjecture holdsMestradoMestre em Ciência da Computaçã