Coloração de Grafos

Coloração de Grafos

Historia

Os primeiro resultados sobre coloração de grafos lidam quase que exclusivamente com grafos planares que foram implementadas na forma de coloração de mapas.
Francis Guthrie postulou a conjectura das quatro cores enquanto tentava colorir um mapa dos condados da Inglaterra. Onde ele afirmou que quatro cores eram suficientes para colorir o mapa, para que as regiões que partilham uma fronteira comum não recebessem uma mesma cor.

Problema de coloração de mapas

Um problema comum que ocorre quando se trabalha com representações de regiões na forma de mapas coloridos é:
“Como representá-las de forma que cada região fique visivelmente clara e distinta das demais?”
A solução deste problema é possível se para cada região for atribuída uma cor e assim cada uma das regiões teria uma coloração distinta das demais. Existe uma técnica de coloração de mapas que diz ser possível colorir qualquer mapa planar utilizando apenas 4 cores.

Conceitos básicos

Seja G=(V,E) um grafo e C um conjunto de cores. Uma coloração de G é uma atribuição de alguma cor de C para cada vértice de G, tal que dois vértices adjacentes sempre possuam cores distintas. Formalmente podemos declarar o problema acima como:

Definição: Uma coloração de um grafo G=(V,E) é uma função , onde C é um conjunto de cores, tal que para cada aresta (v,u) de E tem-se .
Uma k-coloração de G é uma coloração que utiliza k cores.
O número cromático X(G) de um grafo G é o menor número de cores k tal que existe uma k-coloração para G.

Para grafos planares, o problema de coloração está intimamente ligado ao problema das 4 cores em mapas.

Encontrar o número cromático de um grafo é uma tarefa bastante difícil e não é conhecido algoritmo eficiente para realizar esta tarefa. Desta forma tenta-se obter uma aproximação para o problema, objetivando-se encontrar alguma coloração "razoável" para o grafo, ou seja, procura-se o número de cores próximo ao número cromático.

Para