Coloração de vértices

Questões-guia:

1. Defina os seguintes termos: k-coloração; coloração própria; grafo k-colorável; grafo k-partido; número cromático χ(G) de um grafo G.  Dê exemplos.
2. Defina os seguintes termos: grafo k-cromático; coloração ótima; grafo k-crítico.  Dê exemplos.
3. É fácil ou difícil saber se um grafo é 2-colorável?  E 3-colorável?
4. O que é ω(G)?  Qual a relação entre ω(G) e χ(G)?
5. O grau máximo de uma grafo G é denotado por Δ(G).  Qual a relação entre Δ(G) e χ(G)?  Para quais grafos temos χ(G) = Δ(G)+1?
6. Qual é o mínimo número de arestas para um grafo com n vértices e número cromático k?  E o máximo?
7. O que é o polinômio cromático de um grafo?  Qual seria a complexidade de um algoritmo para calculá-lo com base no Teorema 5.3.6?
8. O que é um grafo cordal?  Qual a importância de grafos cordais no estudo do número cromático?

Exercícios:

1. Ex. 5.1.7 do West.
2. Ex. 5.1.29 do West.
3. Implementar MCS (algoritmo 8.1.12 do West) com LEMON.  Faça seu programa receber na linha de comando o grafo em LGF.  Aplique no grafo do exemplo 8.1.13.