O Problema da Coloração de Grafos (GCP, do inglês Graph Coloring Problem) consiste na tarefa de colorir os vértices de um grafo com a menor quantidade possível de cores e de modo que vértices adjacentes recebam cores distintas. Dado que se trata de um problema NP-difícil e, dessa forma, não existir um algoritmo que o resolva em tempo polinomial para todas as instâncias, diversas abordagens são adotadas para, ao menos, soluções aproximadas serem obtidas. A aplicação bem-sucedida de métodos baseados em redes neurais em diferentes domínios tem motivado sua adoção também em problemas de Otimização Combinatória e Teoria dos Grafos, como é o caso do GCP. Nesse contexto, o Aprendizado por Reforço, que também se beneficia da adoção de redes neurais em seus métodos, destaca-se como uma abordagem promissora para o GCP, principalmente por não exigir um conjunto de dados previamente rotulado para o treinamento. Paralelamente, trabalhos na literatura vêm demonstrando que existem arquiteturas específicas de Redes Neurais para Grafos (GNNs, do inglês Graph Neural Networks) adequadas para a resolução de instâncias do GCP. Este projeto visa investigar a integração das melhores práticas oriundas dessas duas abordagens, com o objetivo de aprimorar um algoritmo baseado em redes neurais voltado à resolução de instâncias do GCP, buscando soluções mais eficientes e generalizáveis.