MO405 - Ata de Aula - 2002-10-07

Capítulo 5 Coloração de Grafos

5.1 Coloração de Vértices e Cotas Superiores

Ata

Redator: Luís Augusto Angelotti Meira

Definições

de k-coloração

Cada vértice é colorido com um rótulo, que também chamamos de cor.

k-coloração própria

É um a k-coloração onde vértices adjacentes tem cores diferentes.

k-colorável

Um grafo G é k-colorável se e somente se existe uma k-coloração própria para ele.

número cromático \chi(G)

é o menor k tal que G é k-colorável.

grafo k-cromático

G é k-cromático quando \chi(G) = k

k-crítico

G é k-crítico se e somente se para qualquer H subgrafo de G tal que H é diferente de G temos \chi(H) < \chi(G)

\alpha(G)

tamanho do maior conjunto independente de G

\omega(G)

tamanho do maior conjunto completo, ou clique, de G.

Produto Cartesiano P = (G [] H)

V(P)=V(G) X V(H)
((u,v),(u',v')) pertencem a E(P) se e soemente se u = u' e (v,v') pertencem a E(H) ou v = v' e (u,u') pertencem a E(G)

Exemplo de produto cartesiano entre P3 e C4

Proposiçao: \chi(G) <= \Delta(G)+1

Teorema de Brook's: Se G é um grafo conexo diferente de Kn e C(2n+1) então \chi(G) <= \Delta(G)

Grafo de Intervalos: Seja G um grafo qualquer, se é possível desenhar, para cada vértice de G um segmento na reta real de forma que dois segmentos se interceptem se e somente se exista uma aresta entre os dois vértices correspondentes aos segmentos, então G tem uma representação por intervalos. Um grafo é dito grafo de intervalos quando existe uma tal representação.

Proposição: Se G é um grafo intervalo, então \chi(G) = \omega(G)

Detalhes:

Todo grafo que contenha um Y não é grafo intervalo. Aqui Y é o grafo obtido de K1,3 subdividindo cada aresta com um vértice.
Toda centopéia é grafo de intervalos
Togo grafo que contenha ciclo induzido de tamanho maior que 3 não é grafo de intervalos.

Exemplos de grafos e representação como grafos de intevalos