Coloración de grafos: número cromático

Del mapa al grafo: el problema de coloración

En 1852 Francis Guthrie intentaba colorear un mapa de los condados de Inglaterra de modo que dos condados con frontera en común tuvieran colores distintos. Le preguntó a su hermano Frederick cuántos colores hacían falta. La respuesta —nunca más de cuatro— tardó 124 años en demostrarse formalmente y sigue siendo uno de los resultados más célebres de las matemáticas.

La traducción al lenguaje de grafos es inmediata: cada región del mapa se convierte en un vértice, y dos vértices se conectan con una arista si las regiones comparten frontera. Colorear el mapa equivale a colorear los vértices del grafo de modo que dos vértices adyacentes reciban colores distintos. Esta es la noción de coloración propia.

El mismo problema aparece en contextos aparentemente muy distintos. Organizar horarios de exámenes: dos materias son "incompatibles" si un mismo estudiante las cursa; el número de franjas horarias necesarias es exactamente el número cromático del grafo de incompatibilidades. Asignar frecuencias a antenas de radio que no interfieran: dos antenas son "incompatibles" si sus coberturas se superponen. En todos los casos, la estructura matemática es idéntica.

Las olimpiadas latinoamericanas han explorado este tema repetidamente. En el Cono Sur 2011 y en la Iberoamericana 2017, los problemas de coloración exigían argumentos sobre el número cromático que hoy son técnicas estándar. Dominar esta sección te prepara directamente para esas competencias.

Coloración propia y número cromático: definiciones

Sea $G = (V, E)$ un grafo. Una **$k$-coloración propia** de $G$ es una función $f: V \to \{1, 2, \ldots, k\}$ tal que $f(u) \neq f(v)$ para toda arista $\{u, v\} \in E$. Los valores $1, 2, \ldots, k$ se llaman colores y los conjuntos $f^{-1}(i) = \{v : f(v) = i\}$ son las clases de color o clases cromáticas. Cada clase de color es un conjunto independiente: ningún par de vértices de la misma clase comparte arista.

El número cromático de $G$, denotado $\chi(G)$, es el menor entero $k$ tal que $G$ admite una $k$-coloración propia.

Ejemplos básicos:

(1) $\chi(K_n) = n$. El grafo completo $K_n$ tiene todos los pares de vértices conectados, luego dos vértices cualesquiera son adyacentes y requieren colores distintos. Como hay $n$ vértices, se necesitan $n$ colores. Recíprocamente, asignar un color distinto a cada vértice da una $n$-coloración propia.

(2) $\chi(\text{grafo bipartito}) = 2$ si y solo si el grafo tiene al menos una arista, y $\chi = 1$ si no tiene aristas. Un grafo bipartito con bipartición $(A, B)$ se 2-colorea asignando el color 1 a los vértices de $A$ y el color 2 a los de $B$; ninguna arista conecta dos vértices del mismo color. Recíprocamente, si $\chi(G) = 2$, la bipartición $(f^{-1}(1), f^{-1}(2))$ muestra que $G$ es bipartito.

(3) $\chi(C_n) = 2$ si $n$ es par y $\chi(C_n) = 3$ si $n$ es impar. Para $n$ par, el ciclo $C_n$ es bipartito, luego $\chi = 2$. Para $n$ impar, los vértices del ciclo no pueden 2-colorearse (la 2-coloración alterna colores pero al cerrar el ciclo el primer y el último vértice son adyacentes y tienen el mismo color), luego $\chi \geq 3$; claramente $\chi \leq 3$ usando colores 1, 2, 1, 2, ..., 1, 2, 3.

En general, $\chi(G) \geq \omega(G)$, donde $\omega(G)$ es el número de clique (tamaño del mayor clique), pues los vértices de cualquier clique son mutuamente adyacentes y necesitan colores distintos. También $\chi(G) \geq n / \alpha(G)$, donde $\alpha(G)$ es el número de estabilidad, pues las $\chi(G)$ clases de color tienen tamaño promedio $n / \chi(G) \leq \alpha(G)$.

Coloración codiciosa y la cota $\chi \leq \Delta + 1$

El algoritmo codicioso de coloración (greedy coloring) es el procedimiento más simple para colorear un grafo. Fijamos un orden $v_1, v_2, \ldots, v_n$ de los vértices. Asignamos a cada $v_i$ el menor color positivo que no haya sido usado por ningún vecino ya coloreado de $v_i$ (es decir, ningún $v_j$ con $j < i$ y $\{v_j, v_i\} \in E$).

Teorema: El algoritmo codicioso utiliza a lo sumo $\Delta(G) + 1$ colores, donde $\Delta(G)$ es el grado máximo de $G$. En consecuencia, $\chi(G) \leq \Delta(G) + 1$.

Demostración: Cuando procesamos el vértice $v_i$, tiene a lo sumo $\Delta(G)$ vecinos ya coloreados. Por tanto, los colores usados por sus vecinos ya coloreados forman un conjunto de tamaño a lo sumo $\Delta(G)$. El menor color positivo que no está en ese conjunto es a lo sumo $\Delta(G) + 1$. $\square$

La cota es ajustada: Para $K_n$, $\Delta(K_n) = n-1$ y $\chi(K_n) = n = \Delta + 1$. Para los ciclos impares $C_{2k+1}$, $\Delta = 2$ y $\chi = 3 = \Delta + 1$. El Teorema de Brooks (Lección 2.2) caracteriza exactamente cuándo vale la igualdad.

El orden importa: La coloración codiciosa puede dar resultados distintos según el orden de los vértices. Un orden óptimo (que use exactamente $\chi(G)$ colores) siempre existe, pero encontrarlo puede ser difícil en general. En la práctica olímpica, el truco es elegir el orden que más convenga al argumento: por ejemplo, ordenar los vértices de mayor a menor grado (orden de Welch-Powell) tiende a usar pocos colores.

Coloración por grado mínimo: Existe siempre un orden tal que el codicioso usa a lo sumo $\delta^* + 1$ colores, donde $\delta^* = \max_{H \subseteq G} \delta(H)$ es el mayor grado mínimo sobre todos los subgrafos. Para obtenerlo, construimos el orden de derecha a izquierda: en cada paso, tomamos el vértice de menor grado en el subgrafo restante y lo añadimos al inicio de la lista. Este argumento mejora a veces la cota $\Delta + 1$.

El Teorema de los Cuatro Colores y coloraciones de mapas

El Teorema de los Cuatro Colores (4CT) establece que todo grafo plano admite una 4-coloración propia. En términos de mapas, esto dice que todo mapa geográfico puede colorearse con cuatro colores de modo que regiones fronterizas tengan colores distintos.

Historia: Conjeturado en 1852, el 4CT fue demostrado por Appel y Haken en 1976 mediante una verificación asistida por computadora de 1476 configuraciones reducibles. La prueba no fue verificada por completo manualmente hasta décadas después; en 2005, Gonthier formalizó la prueba en el asistente de demostraciones Coq. Es uno de los primeros teoremas matemáticos relevantes en ser demostrado computacionalmente.

El Teorema de los Cinco Colores (5CT) tiene una demostración clásica a mano, adecuada para olimpiadas de alto nivel. La clave es el Lema de Euler para grafos planos: todo grafo plano conexo con $n$ vértices, $m$ aristas y $f$ caras satisface $n - m + f = 2$ (Fórmula de Euler). De aquí se deriva que todo grafo plano tiene un vértice de grado a lo sumo 5. La prueba del 5CT procede por inducción: elimina ese vértice de grado $\leq 5$, colorea el grafo restante con 5 colores, y re-inserta el vértice. Si sus $\leq 5$ vecinos usan $\leq 4$ colores, hay uno disponible. Si usan exactamente 5 colores, un argumento de "cadenas de Kempe" permite recolorear y liberar un color.

Grafos planos y mapas: Un grafo es plano si puede dibujarse en el plano sin que sus aristas se crucen. Todo mapa geográfico (con regiones conexas) corresponde a un grafo plano: los vértices son las regiones y las aristas conectan regiones con frontera común. La condición "no cruce" refleja la planariedad del mapa. Los grafos no planos (como $K_5$ y $K_{3,3}$) no corresponden a ningún mapa geográfico.

Relevancia olímpica: El 4CT en sí no se pide demostrar en olimpiadas (su prueba es inabordable a mano), pero el Teorema de los Cinco Colores y la fórmula de Euler sí aparecen. Más aún, la estructura de grafos planos y la cota de $leq 5$ en el grado mínimo son herramientas estándar para problemas de nivel IbAm.

Problema trabajado: número cromático del grafo de Petersen

El grafo de Petersen $P$ es un grafo cúbico (3-regular) con 10 vértices y 15 aristas. Es uno de los grafos más estudiados en combinatoria por sus propiedades extremales: es el grafo cúbico más pequeño que no es 3-coloreable en aristas (es decir, tiene índice cromático 4). ¿Cuál es su número cromático (de vértices)?

Descripción del grafo de Petersen: Los 10 vértices se organizan en dos anillos: el externo $\{v_1, v_2, v_3, v_4, v_5\}$ forma un ciclo $C_5$, y el interno $\{u_1, u_2, u_3, u_4, u_5\}$ forma un "pentaciclo estrella" (cada $u_i$ está conectado a $u_{i+2}$ y $u_{i+3}$ módulo 5, formando un $C_5$ de diagonales). Además, cada $v_i$ está conectado a $u_i$.

Paso 1 — Cota inferior: El grafo de Petersen no es bipartito (contiene ciclos impares), luego $\chi(P) \geq 3$. De hecho, el ciclo exterior $v_1, v_2, v_3, v_4, v_5$ tiene longitud 5 (impar), así que $\chi(C_5) = 3$. Como $C_5$ es subgrafo de $P$, $\chi(P) \geq 3$.

Paso 2 — Exhibir una 3-coloración: Asignamos colores $\{R, V, A\}$ a los vértices. Para el ciclo externo $C_5$: $v_1 = R$, $v_2 = V$, $v_3 = R$, $v_4 = V$, $v_5 = A$. Para el ciclo interno (recordemos que $u_i$ está conectado a $v_i$, $u_{i+2}$ y $u_{i+3}$): $u_1 = A$ (distinto de $v_1 = R$), $u_2 = A$ (distinto de $v_2 = V$), $u_3 = V$ (distinto de $v_3 = R$, $u_1 = A$, $u_5 = ?$). Procedemos cuidadosamente: $u_1 = A$, $u_2 = R$, $u_3 = A$... el anillo interno forma el pentágono $u_1 u_3 u_5 u_2 u_4 u_1$ (conectando $u_i$ con $u_{i+2 \bmod 5}$). Ese pentágono tiene coloración: $u_1 = A$, $u_3 = R$, $u_5 = A$, $u_2 = V$, $u_4 = R$. Verificamos la compatibilidad: aristas del interno: $u_1$-$u_3$: A vs R ✓; $u_3$-$u_5$: R vs A ✓; $u_5$-$u_2$: A vs V ✓; $u_2$-$u_4$: V vs R ✓; $u_4$-$u_1$: R vs A ✓. Aristas radiales: $v_1$-$u_1$: R vs A ✓; $v_2$-$u_2$: V vs V ✗. Ajustamos $u_2 = A$: $v_2$-$u_2$: V vs A ✓; $u_5$-$u_2$: A vs A ✗. Ajustamos $u_5 = R$: $u_3$-$u_5$: R vs R ✗. La asignación requiere más cuidado.

Coloración correcta: Etiquetemos los vértices del Petersen como $\{0,1,2,3,4\}$ (externos) y $\{5,6,7,8,9\}$ (internos), con aristas externas $\{i, i+1 \bmod 5\}$, internas $\{i+5, i+7 \bmod 5 + 5\}$ y radiales $\{i, i+5\}$. Asignación: $f(0)=1, f(1)=2, f(2)=1, f(3)=2, f(4)=3, f(5)=2, f(6)=3, f(7)=3, f(8)=1, f(9)=1$. Verificación completa: externas: (0,1)=1,2✓; (1,2)=2,1✓; (2,3)=1,2✓; (3,4)=2,3✓; (4,0)=3,1✓. Internas: (5,7)=2,3✓; (6,8)=3,1✓; (7,9)=3,1✓; (8,5)=1,2✓; (9,6)=1,3✓. Radiales: (0,5)=1,2✓; (1,6)=2,3✓; (2,7)=1,3✓; (3,8)=2,1✓; (4,9)=3,1✓. Todas las aristas son válidas.

Conclusión: $\chi(\text{Petersen}) = 3$. El grafo de Petersen es 3-coloreable pero no 2-coloreable (no es bipartito). Esto ilustra que $\chi(G) = \omega(G)$ no siempre vale: $\omega(\text{Petersen}) = 2$ (no contiene triángulos) pero $\chi = 3$.

Estrategia olímpica: identificar $\chi$ con cotas cruzadas

En olimpiadas, determinar $\chi(G)$ generalmente requiere dos pasos: (1) demostrar $\chi(G) \geq k$ exhibiendo una obstrucción (un subgrafo que requiere $k$ colores), y (2) demostrar $\chi(G) \leq k$ exhibiendo una $k$-coloración explícita.

Cotas inferiores estándar: $\chi(G) \geq \omega(G)$ (tamaño del mayor clique). $\chi(G) \geq \lceil n / \alpha(G) \rceil$ (densidad). $\chi(G) \geq 3$ si $G$ contiene un ciclo impar. $\chi(G) = 1$ solo si $G$ no tiene aristas. Estas cotas son fáciles de calcular y suelen ser suficientes en problemas olímpicos.

Cotas superiores estándar: $\chi(G) \leq \Delta(G) + 1$ (greedy). $\chi(G) \leq 4$ para grafos planos (4CT). $\chi(G) = 2$ si $G$ es bipartito. Construir una coloración explícita es siempre una prueba válida de $\chi(G) \leq k$.

Truco de la inducción sobre vértices: Para demostrar $\chi(G) \leq k$, a menudo es efectivo inducir sobre $|V|$: eliminar un vértice $v$ de grado bajo ($d(v) \leq k-1$), colorear el resto por hipótesis inductiva con $k$ colores, y asignar a $v$ cualquier color no usado por sus $\leq k-1$ vecinos. Esto reproduce exactamente la prueba del teorema $\chi \leq \Delta + 1$ en su forma inductiva.

Ejemplo de síntesis (Cono Sur 2011, P3, adaptado): Un grafo $G$ tiene $n$ vértices y grado mínimo $\delta \geq n/2$. Demuestra que $\chi(G) \leq 3$ si $G$ no contiene $K_4$. Solución: como $\delta \geq n/2$, el grafo es conexo (por el argumento del Capítulo 1). Si $G$ no contiene $K_3$ (triángulo), es bipartito y $\chi = 2$. Si $G$ contiene un triángulo pero no $K_4$, se usa la cota de Brooks (próxima lección): $\Delta \leq n-1$ y el grafo no es completo ni ciclo impar, luego $\chi \leq \Delta \leq n-1$. Una construcción más cuidadosa usando la ausencia de $K_4$ y la densidad alta da $\chi \leq 3$.

Resumen: Las herramientas de esta lección son: definición de coloración propia, fórmulas $\chi(K_n) = n$, $\chi(\text{bipartito}) = 2$, $\chi(C_{2k+1}) = 3$, cota greedy $\chi \leq \Delta + 1$, enunciado del 4CT, y cálculo de $\chi$ mediante cotas cruzadas. La siguiente lección profundiza cuándo la cota $\chi \leq \Delta + 1$ se puede mejorar a $\chi \leq \Delta$ (Teorema de Brooks).