Modelagem matemática e aplicações do problema de coloração em grafos

Abstract

O objetivo desse trabalho é apresentar o problema de coloração em grafos sob diferentes perspectivas. Caracterizamos o polinômio cromático de um grafo e enunciamos algumas de suas propriedades. Apresentamos duas formulações matemáticas para o problema de coloração de vértices e um método de solução para cada formulação. Apresentamos e discutimos propostas de atividades para o desenvolvimento de uma Oficina de Coloração para alunos do Ensino Médio e Fundamental.

In this work the graph coloring problem was presented under di erent perspectives. We define the chromatic polynomials of a graph and describe some of its properties. Furthermore, two solution methods for the vertex coloring problem, through integer programming formulation, has been presented. We propose and discuss some activities for the development of a Workshop for students of secondary school.