Um dos problemas mais famosos da Teoria dos Grafos é o Problema das Quatro Cores, que teve sua origem em 1852, quando Francis Guthrie conjecturou que todo mapa pode ser colorido com quatro cores, de forma que regiões vizinhas tenham cores distintas. O Problema das Quatro Cores consiste em determinar a veracidade da conjectura e permaneceu sem solução até 1976, quando Haken e Appel provaram que a conjectura é, de fato, verdadeira.

As tentativas de solução do Problema das Quatro Cores durante mais de um século contribuíram significativamente para o desenvolvimento da Teoria dos Grafos, dando origem a muitos dos conceitos, teoremas e problemas da área. Na tentativa de resolver o Problema das Quatro Cores, Alfred Bray Kemp o modelou como um grafo, onde cada região é representada por um vértice e existe uma aresta {u,v} se as regiões representadas pelos vértices u e v são vizinhas no mapa. Kemp mostrou que o Problema das Quatro Cores é equivalente ao problema de determinar se um grafo construído a partir de um mapa pode ter seus vértices coloridos utilizando-se quatro cores, de forma que vértices vizinhos tenham cores distintas. O modelo de Kemp deu origem a um novo problema, que ficou conhecido como Problema da Coloração de Vértices, que consiste em determinar, dado um grafo, qual o menor número de cores necessárias para se colorir seus vértices de forma que vértices vizinhos tenham cores distintas.

Outra tentativa de resolver o Problema das Quatro Cores, feita por Tait, baseou-se em um modelo onde o mapa é transformado em um grafo no qual deseja-se atribuir cores às arestas de forma que arestas incidentes em um mesmo vértice tenham cores diferentes. Tait mostrou que o número de cores necessárias para colorir as arestas do grafo gerado é o mesmo número de cores necessárias para colorir as regiões do mapa original. O modelo de Tait deu origem a outro problema, que ficou conhecido como Problema da Coloração de Arestas e consiste em determinar, dado um grafo, quantas cores são necessárias para colorir suas arestas de forma que arestas incidentes em um mesmo vértice tenham cores distintas.

Em 1965 os problemas da coloração de vértices e de arestas foram generalizados, por Behzad e Vizing, independentemente, que introduziram o Problema da Coloração Total, onde se pretende determinar, dado um grafo, quantas cores são necessárias para colorir seus vértices e suas arestas de forma que dois vértices vizinhos tenham cores distintas, duas arestas incidentes em um mesmo vértice tenham cores distintas e cada aresta tenha cor diferente das cores dos dois vértices em que incide.

Muitas outras variantes de problemas de coloração em grafos surgiram nas últimas décadas. Tais problemas modelam inúmeras aplicações relacionadas à otimização no uso de recursos com restrições de compartilhamento, como escalonamento de tarefas, alocação de equipamentos, criação de tabelas de torneios, projetos de circutos eletrônicos, de redes elétricas e de redes de comunicação. Apesar da larga aplicabilidade dos problemas de coloração em grafos, vários deles têm uma versão de decisão que é um problema NP-completo, o que implica que até o momento não conhecemos soluções computacionais eficientes para resolver tais problemas. Mais que isso, uma solução computacional eficiente para qualquer problema NP-Completo, como as versões de decisão dos problemas de coloração de vértices, de arestas e total, implica na existência de solução computacional eficiente para muitos outros problemas amplamente conhecidos e pesquisados, que também modelam muitos problemas reais, como o Problema da Satisfatibilidade, do Caixeiro Viajante e da Mochila.

Este projeto pretende contribuir para o avanço do conhecimento da Teoria de Grafos e, consequentemente, da Teoria da Computação, buscando algoritmos polinomiais para resolver problemas de coloração em classes de grafos largamente estudadas, que possuem propriedades estruturais bem definidas e para as quais tais problemas permanecem em aberto.