Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/276119
Type: TESE
Title: Sobre grafos perfeitos
Author: Mendonça Neto, Candido Ferreira Xavier de, 1959-
Advisor: Lucchesi, Cláudio Leonardo, 1945-
Abstract: Resumo: 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 vale

Abstract: 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 holds
Subject: Teoria dos grafos
Transformações (Matemática)
GRAFO (Sistema de computador)
Language: Português
Editor: [s.n.]
Date Issue: 1987
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
MendoncaNeto_CandidoFerreiraXavierde_M.pdf1.19 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.