Algoritmos Exatos para Problema de Coloração em Grafos

Colorir um grafo significa pintar cada um dos seus vértices com uma cor, de forma tal que, se dois vértices quaisquer são adjacentes, então eles recebem cores distintas. Neste trabalho, realizamos um estudo sob forma de levantamento entre os diversos métodos que solucionam, de maneira exata, o problema de encontrar o número mínimo de cores, chamado número cromático, necessárias para colorir um grafo qualquer. Além deste, analisamos os algoritmos exatos para outros dois problemas de coloração em grafos: a 3-coloração e a 4-coloração. Propomos ainda, um novo algoritmo para verificar se um grafo pode ser colorido com três cores.