Master's Dissertation
DOI
https://doi.org/10.11606/D.45.2005.tde-20210729-144309
Document
Author
Full name
Daniel Morgato Martin
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2005
Supervisor
Title in Portuguese
Coloração de grafos e método probabilÃstico
Keywords in Portuguese
Teoria Dos Grafos
Abstract in Portuguese
Nesta dissertação estudamos alguns problemas envolvendo coloração de grafos, e focamos em alguns resultados a respeito desse assunto que usam o método probabilÃstico. Vamos, primeiramente, demonstrar o Teorema de Brooks e o Teorema de Vizing, que são os dois primeiros resultados que qualquer estudante da área vê a respeito de coloração de vértices e arestas respectivamente. Em seguida, introduzimos o conceito de lista-coloração e mostramos uma prova do Teorema de Galvin, que até recentemente era um problema em aberto. O Teorema de Galvin afirma que para qualquer grafo bipartido G, o número cromático e o número lista-cromático são iguais. Ainda na primeira parte do texto, explicamos o que é coloração total e enunciamos a principal conjectura que existe a respeito desse assunto. Depois disso, numa segunda parte do texto, fazemos um resumo de conceitos probabilÃsticos e de algumas ferramentas como o Lema Local e algumas desigualdades importantes. Esses conceitos são usados no restante do texto. Em seguida, mostramos algumas aplicações do método probabilÃstico para resolver problemas de lista-coloração e problemas de coloração total.
Title in English
not available
Abstract in English
not available
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2021-07-29