Coloreo de grafos

De Wikipedia, la enciclopedia libre

En la teoría de grafos, uno de los problemas más interesantes es el de coloreo, coloración o coloreado de grafos. El objetivo de este problema consiste en asignarle distintos colores (o números enteros) a los vértices de un grafo, de manera que ningún par de vértices adyacentes compartan el mismo color o número.

El problema puede plantearse también para aristas o para caras de la inmersión plana de un grafo, siendo el desarrollo muy similar al coloreo de vértices.

[editar] Número cromático

Un grafo se denomina k-coloreado si puede colorearse con k colores distintos. Es decir, si existe una asignación de k colores diferentes que permitan un coloreo válido de un grafo G. Se llama coloreo válido al coloreo que cumple la propiedad ya mencionada de no asignar el mismo color a un par de vértices adyacentes.
El número cromático de un grafo es el menor número natural k entre todos los valores posibles que permiten k-colorear un grafo. Se denomina a este valor como $Χ(G)$ .

[editar] Propiedades y teoremas

Existe un teorema fundamental de esta teoría, denominado teorema de los cuatro colores que afirma que todo grafo planar puede colorearse con, a lo sumo, 4 colores distintos. Entre las distintas propiedades que existen para el número cromático, se pueden mencionar las siguientes:

Para un grafo completo $K n$ , $Χ(K n) = n$ . Esto se puede ver intuitivamente, ya que un grafo completo tiene todos sus nodos conectados entre sí, es decir, $\forall u, v \in V_G \Rightarrow (u,v) \in E_G$ . Por lo tanto, como un coloreo válido obliga a que dos nodos adyacentes tengan colores distintos, se necesitan n colores distintos para formar un coloreo válido de G, y este es el menor número posible. Luego, $Χ(G) = n$ .
Si G es un ciclo de longitud par, entonces $Χ(G) = 2$ .
Si G es un ciclo de longitud impar, entonces $Χ(G) = 3$ .
Para todo grafo G, $\Chi{(G)} \ge \omega{(G)}$ , donde $ω(G)$ corresponde al valor de la cliqué de mayor orden de un grafo.
Para todo grafo G, $\Chi{(G)} \le \Delta{(G)}$ ó $\Chi{(G)} \le \Delta{(G)} + 1$ , donde $Δ(G)$ es el máximo entre los grados de todos los nodos (es decir, el grado máximo).