O Problema da Partição Cromática de Custo Mínimo (PPCCM), considerado uma das diversas variantes do Problema Clássico de Coloração de Grafos (PCG), utiliza nú- meros reais como custos das cores, tendo como objetivo colorir os vértices de um grafo de modo que os adjacentes tenham cores diferentes e a soma dos custos das cores utilizadas seja mínima. Embora seja um problema NP-Difícil para grafos em geral, foram elaborados algoritmos polinomiais para algumas classes de grafos. Do ponto de vista prático, o mesmo foi empregado no projeto de circuitos VLSI e na solução de determinados problemas de escalonamento modelados como grafos de intervalo. Nesta tese são propostos algoritmos para o PPCCM considerando um grafo simples não-direcionado como entrada. Inicialmente foram desenvolvidas duas heurísticas baseadas na metaheurística Algoritmos Genéticos com Chaves Aleatórias Tendenciosas (Biased Random Key Genetic Algorithms - BRKGA, em inglês). Posteriormente, foi implementada uma heurística de trajetória que faz uso de duas estratégias de busca local seguidas por um procedimento de path-relinking. Para os experimentos computacionais foram geradas instâncias para o problema a partir de grafos comumente empregados no PCG.