Coloração de grafos e método probabilístico

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. (AU)