Coloración de grafos

El coloreo, coloración o coloreado de grafos es uno de los problemas más interesantes de la teoría de grafos. El objetivo de este problema consiste en asignar 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.

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 que cumple la propiedad 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 $\mathrm {X} {(G)}$.

Teoremas

Ejemplo de mapa coloreado con cuatro colores.

Existe un teorema fundamental de esta teoría, denominado teorema de los cuatro colores que afirma que todo grafo plano puede colorearse con, a lo sumo, cuatro colores distintos.

Propiedades

Entre las propiedades del número cromático, se pueden mencionar las siguientes:

• Para un grafo completo $K_{n}\,$, $\mathrm {X} {(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, $\mathrm {X} {(G)}=n\,$

• Si G es un ciclo de longitud par, entonces $\mathrm {X} {(G)}=2\,$
• Si G es un ciclo de longitud impar, entonces $\mathrm {X} {(G)}=3\,$
• Para todo grafo G, $\mathrm {X} {(G)}\geq \omega {(G)}$, donde $\omega {(G)}\,$ corresponde al valor de la cliqué de mayor orden de un grafo.
• Para todo grafo G, $\mathrm {X} {(G)}\leq \Delta {(G)}$ ó $\mathrm {X} {(G)}\leq \Delta {(G)}+1$, donde $\Delta {(G)}\,$ es el máximo entre los grados de todos los nodos (es decir, el grado máximo).