Seminário de Otimização Combinatória

              Duas novas formulações inteiras 0-1 
           para o problema de coloração de vértices.

                  Rosa Maria Videira de Figueiredo
           Universidade do Estado do Rio de Janeiro-UERJ

                      Sexta-feira, 7 de junho
                     sala: IC2-96 horario: 18hs


Resumo:
=======

O problema de coloração de vértices é um dos problemas mais conhecidos
em teoria dos grafos. Neste trabalho são apresentados dois novos
modelos de programação linear inteira para este problema.  A motivação
para estes modelos é um resultado apresentado por Deming em 1979, que
descreve o problema de coloração como um problema de otimização
definido sobre o conjunto das orientações acíclicas do grafo que se
deseja colorir.  Com a intenção de desenvolvermos um método de planos
de cortes para o problema de coloração de vértices iniciamos o estudo
do poliedro associado com um dos modelos propostos.