Teoria dos Grafos  - Coloração

---

_Coloração

_{Dado o Grafo:}

 

_{Colorindo os Vértices}

 

_{Colorindo  as Arestas}

 

_{Coloração de Vértices}

_{Uma coloração de um grafo G é uma função cor, sobrejetiva, de VG em um conjunto finito C = { c1,c2,,...,cn } chamado de conjunto de cores, de tal modo que, dados dois vértices u e v ∈ VG, se u é adjacente a v então cor(u) ≠ cor(v), em outras palavras, devemos colorir cada vértice de G de tal modo que se dois vértices forem adjacentes, as suas cores devem ser diferentes.
É claro que todo Grafo com k vértices pode ser colorido com k cores.}
 

 

_{Cor : Função Sobrejetiva}
se (u,v) AG então

f(u,v) f(v)

_{Número Cromático ( χ )}

_{É o menor número de cores com que é possível colorir um Grafo.
 χ (G) = k, dizemos que G é k-cromático.
Nos grafos bipartidos χ (G) = 2.}
 

_{A coloração abaixo é a menor coloração de vértices para o grafo?}
 

_{Não, pois essa coloração utiliza quatro cores e a figura abaixo mostra que é possível colorir o mesmo grafo com apenas duas cores.}
 
 
 
 
 

_{Exercício: Provar que os Bipartidos são 2-Cromáticos}

_{Como colorir um Bipartido -> Uma cor para uma partição e outra cor para outra}

 

_{Alguns limites}

•   _{χ(G) ≥ ω(G), onde w (G) é o tamanho de uma clique máxima em G.}


 _{Obs:Uma clique, no grafo G, é o conjunto de vértices de um subgrafo induzido completo, em G. Uma clique x é máxima quando não existe outra clique, no mesmo grafo, com um número maior de vértices. Uma clique é maximal quando não está contida em outra clique (alguns autores utilizam o termo "clique" no lugar de "clique maximal")}
 
 

_{Coloração de Arestas}

• _{Dado um grafo simples G. Uma k-coloração de arestas de G é uma atribuição de k-cores as arestas de G de tal modo que a quaisquer duas arestas adjacentes sejam atribuidas cores distintas.}
• _{O índice cromático de um Grafo G é o menor k para o qual G possui uma k-coloração de arestas. Denota-se por χ'(G).}

_{Teorema de Vizing: Δ(G) &ge χ'(G) &le Δ(G)+1}