Número cromático e coloração de um grafo

Número cromático de um grafo representa o menor número de cores necessárias para colorir os vértices de um grafo sem que vértices adjacentes tenham a mesma cor.

Consideremos os seguintes grafos:





Número de cores ( n ) = 2





Número de cores ( n ) = 4












Coloração em Grafo


Uma coloração de um grafo é uma atribuição de cores aos vértices, de modo que vértices adjacentes tenham cores distintas.


Um grafo G tem k-coloração se ele pode ser colorido com k cores.

• Um grafo G tem k-coloração significa que o grafo admite uma coloração mínima de k cores.Assim, definimos:

– O número cromático de G é k.

– G é k-cromático.

– c(G) = k .