Problemas de Coloração em Grafos

Neste trabalho apresentamos modelos e algoritmos para problemas relacionados ao problema de coloração em grafos. Três problemas foram estudados: O Problema de Coloração Particionada (PCP), o Problema de Coloração Equilibrada (PCE) e o Problema de Alocação de Freqêencias (PAF). Na tese, introduzimos modelos de programação linear inteira e discutimos seu uso na solução de aplicações práticas. Apresentamos um estudo parcial do poliedro associado ao modelo PCP e introduzimos novas classes de desigualdades válidas para os demais modelos. Finalmente, descrevemos a implementação de um algoritmo branch and cut que utiliza os modelos apresentados, analisando suas vantagens e limitações.