Politopo baseado em distâncias para o problema clássico de coloração de vértices em grafos

• Bruno Dias
• Rosiane de Freitas
• Javier Marenco
• Nelson Maculan

DOI: https://doi.org/10.5753/etc.2018.3157

Resumo

Neste trabalho, apresenta-se o modelo baseado em distâncias para o problema clássico de coloração de vértices em grafos (VCP). A formulação de programação linear inteira utiliza variáveis de decisão que representam a distância entre cores atribuídas para cada par de vértices distintos, no lugar de fornecer explicitamente tais cores. Mostra-se que há uma relação próxima entre esta formulação e o modelo baseado em orientação para o VCP, proposto também pelos autores deste trabalho. Em particular, prova-se que desigualdades indutoras de facetas para o modelo baseado em orientação podem ser traduzidas em desigualdades indutoras de facetas para o modelo baseado em distâncias e vice-versa.