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 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 ejes o regiones de un grafo planar, siendo el desarrollo muy similar al coloreo de vértices. Sin embargo, es éste método el más estudiado.

[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).