Formulações de programação inteira para o problema da coloração de Grundy

Dado um grafo G=(V,E), o problema da coloração de Grundy consiste em encontrar uma atribuição de cores a cada um de seus vértices de forma que vértices adjacentes recebam cores diferentes, e as regras da heurística first-fit sejam respeitadas. Tais regras implicam que uma dada cor, exceto a de menor índice, só pode ser utilizada para um vértice se todas as outras cores de índice inferior estiverem presentes na sua vizinhança. Sua solução ótima define o número de Grundy Γ(G) de um grafo, o qual fornece um limite de pior caso para o desempenho da abordagem gulosa first-fit para o conhecido problema da coloração de vértices. Neste trabalho, são propostas formulações de programação inteira, padrão e por representativos, para o problema da coloração de Grundy. Experimentos computacionais preliminares indicam que a formulação por representativos tem desempenho melhor do que uma formulação padrão, especialmente em grafos mais densos.