Coloreo de grafos — número cromático y aplicaciones

El coloreo de grafos normalmente significa coloreo de vértices: asignar un color a cada vértice de modo que los vértices adyacentes no compartan color. El menor número de colores que funciona es el número cromático, escrito $\chi(G)$.

Si quieres la intuición rápida, los colores son solo etiquetas sin conflictos. Dos vértices pueden reutilizar el mismo color exactamente cuando no hay una arista entre ellos.

Definición de coloreo de grafos en un minuto

En un coloreo propio, cada arista conecta dos vértices de distinto color. Esa es toda la regla.

Así que si $\chi(G)=3$, dos hechos son ciertos al mismo tiempo:

• existe un coloreo propio con $3$ colores
• no existe un coloreo propio con solo $2$ colores

Por eso el número cromático es un mínimo, no solo la cantidad de colores que casualmente usaste en un dibujo.

A menos que alguien diga lo contrario, en un curso introductorio el coloreo de grafos significa colorear los vértices de un grafo simple no dirigido. El coloreo de aristas es un problema distinto con reglas diferentes.

Qué está midiendo realmente el número cromático

Los nombres de los colores no importan. Puedes usar rojo, azul y verde, o las etiquetas $1$, $2$ y $3$.

Lo que importa es la agrupación. Todos los vértices con el mismo color forman un conjunto sin aristas internas, así que ese grupo no tiene conflictos.

Esa forma de verlo es lo que hace útil el coloreo de grafos en problemas de planificación y asignación. Un color a menudo significa “estos elementos pueden compartir el mismo turno”.

Ejemplo resuelto: por qué un ciclo de 5 necesita 3 colores

Considera el grafo ciclo $C_5$ con aristas $AB, BC, CD, DE,$ y $EA$.

Prueba primero con $2$ colores. Da a $A$ el color $1$ y a $B$ el color $2$. Entonces el coloreo queda forzado alrededor del ciclo:

$$A=1,\quad B=2,\quad C=1,\quad D=2$$

Ahora mira $E$. Es adyacente tanto a $D$ como a $A$, así que no puede usar el color $2$ por $D$, y no puede usar el color $1$ por $A$.

Así que $2$ colores no bastan.

Pero $3$ colores sí funcionan. Un coloreo propio es

$$A=1,\quad B=2,\quad C=1,\quad D=2,\quad E=3$$

por lo tanto

$$\chi(C_5)=3$$

Vale la pena recordar este ejemplo porque muestra un patrón importante: en los grafos ciclo, un ciclo par puede colorearse con $2$ colores, pero un ciclo impar necesita $3$.

Cómo razonar sobre el coloreo de grafos pequeños

Dos comprobaciones rápidas ayudan.

Primero, busca un conflicto forzado. En el ejemplo anterior, alternar dos colores alrededor de un ciclo impar hace que el último vértice entre en conflicto con las dos opciones disponibles.

Segundo, busca una cota inferior. Si un grafo contiene un triángulo, entonces esos tres vértices son adyacentes por pares, así que ya necesitan $3$ colores distintos. Eso no siempre da la respuesta exacta, pero demuestra que el número cromático es al menos $3$.

Errores comunes en problemas de coloreo de grafos

Un error común es tratar vértices como adyacentes solo porque están dibujados cerca. Solo una arista real crea una restricción de coloreo.

Otro error es suponer que cada vértice necesita su propio color. Los vértices no adyacentes pueden reutilizar un color, y los coloreos eficientes suelen reutilizar colores tanto como sea posible.

A veces los estudiantes también confunden el coloreo de vértices con el coloreo de aristas. En esta página, la regla trata sobre vértices adyacentes, no sobre aristas adyacentes.

Un último error es informar la cantidad de colores que casualmente usaste en lugar del número mínimo requerido. Usar $4$ colores en un grafo no demuestra que el número cromático sea $4$.

Dónde se usa el coloreo de grafos

Una aplicación estándar es la planificación de horarios. Supón que cada vértice es un examen, y una arista significa que dos exámenes comparten estudiantes y no pueden programarse al mismo tiempo. Entonces un color puede representar una franja horaria.

En ese modelo, el número cromático te dice el menor número posible de franjas horarias. Si $\chi(G)=4$, entonces no existe un horario válido con solo $3$ franjas.

La misma idea aparece en el coloreo de mapas, donde las regiones vecinas deben ser distintas, y en el diseño de compiladores, donde las variables que se necesitan al mismo tiempo no pueden compartir el mismo registro.

Prueba un problema similar de coloreo de grafos

Dibuja un grafo con vértices $P,Q,R,S,T$ y aristas $PQ, QR, RS, ST, TP,$ y $PR$.

Empieza encontrando un triángulo para obtener una cota inferior. Luego intenta colorear el grafo con la menor cantidad de colores posible y comprueba si algún par de vértices adyacentes coincide. Si quieres un paso más, prueba tu propia versión en un grafo más grande y mira si puedes demostrar que tu coloreo es mínimo, no solo válido.