Um dos problemas mais populares e amplamente estudados em Teoria de Grafos é o problema de coloração de grafos (PCG), que conta com amplas aplicações práticas na atualidade. Dentre as variantes do PCG encontra-se o Problema de Coloração Harmônica de Grafos (PCHG), que propõe colorir os vertices (nós) de um grafo com o menor número de cores possíveis de maneira que as arestas sejam únicas e distinguíveis pelo conjunto de cores dos vértices de suas pontas, ainda que nós adjacentes no grafo tenham as mesmas cores – o que difere do problema de coloração usual, pois gera uma coloração não-própria. A literatura sobre o Problema de Coloração Harmônica de Grafos ainda hoje carece de trabalhos em Pesquisa Operacional a respeito, assim como escasseiam soluções heurísticas dedicadas ao problema, sendo elas majoritariamente adaptações de soluções para o PCG. Em contraponto, este trabalho propõe uma heurística gulosa dedicada a resolução do PCHG e apresenta os resultados por ela obtidos frente a instancias distintas de grafos de teste.