Coloração em Grafos

Algoritmo de Coloração utilizando busca em profundidade

Programa Principal
	montar a lista de adjacências
	inicializar a estrutura de cores
	escolher o vertice Vi de maior grau para ser colorido primeiro
	chamar a sub-rotina Colore_Vertice para colorir o vertice Vi escolhido

Sub-rotina Colore_Vertice: Vk
se o vertice Vk ainda nao foi colorido
	procurar a cor C apropriada
	se nao existir cor apropriada para colorir o vertice Vk
	criar uma nova cor C
	fim se
	colorir o vertice Vk com a cor C
	para todo vertice Vj adjacente a Vk faça
	chamar a sub-rotina Colore_Vertice para colorir o vertice Vj
fim se

Algoritmo Passo a Passo

Número Cromático = 4

Custo Computacional

Considerando que N seja o número de vértices, E o número de arestas, NC seja o número de cores e NVZ seja o número de vizinhos(vértices adjacentes), temos:
1. montar a lista de adjacência= O(N+E)
2. escolher o vertice de maior grau= O(N)
3. procurar cor= O(NVZ*NC)
4. colorir o vertice= O(1)
5. para todos os vertices colorir todos os seus adjacentes: O((N-1)*(NVZ*NC))

Custo Total= O(N+E) + O(N) + O(N*(NVZ*NC))
de onde podemos concluir que o custo total é da ordem de O(N*(NVZ*NC)), em que no pior caso teremos um custo de ordem cúbica.