Número Cromático

Teoría

El número cromático de una gráfica $G$, que escribes como $\chi(G)$, es el entero $k$ más pequeño tal que la gráfica se puede colorear con $k$ colores. Decimos que una gráfica es $k$-coloreable si puedes asignar a sus vértices uno de $k$ colores de forma que no haya dos vértices adyacentes con el mismo color. A esta asignación la conocemos como una coloración propia de vértices. Si los vértices adyacentes $u$ y $v$ tienen colores $c(u)$ y $c(v)$, la condición pide que $c(u) \neq c(v)$ para todas las aristas $(u,v) \in E$.

Este concepto es fundamental en optimización combinatoria y sirve para modelar problemas de resolución de conflictos. Por ejemplo, si los vértices representan eventos y las aristas representan conflictos de horario, $\chi(G)$ representa el número mínimo de espacios de tiempo que necesitas para programar todos los eventos sin que se encimen. Intuitivamente, el número cromático mide la "densidad local" o la complejidad estructural de una gráfica. Un número cromático alto implica que la gráfica tiene subestructuras densas donde muchos vértices están conectados entre sí, lo que hace imposible separarlos en unos pocos conjuntos independientes.

Determinar el número cromático exacto de una gráfica cualquiera es un problema NP-duro, lo que significa que no se conoce ningún algoritmo general que sea eficiente. Por eso, en las olimpiadas de matemáticas (como el AIME o la USAMO), los problemas suelen enfocarse en encontrar cotas superiores e inferiores para $\chi(G)$ usando otros invariantes de la gráfica como el grado máximo $\Delta(G)$, el número de clan $\omega(G)$ o el número de independencia $\alpha(G)$. Entender cómo interactúan estos invariantes es la clave para resolver problemas avanzados de coloración.

Fórmulas Clave

Cotas Básicas Para una gráfica $G$ con $n$ vértices y grado máximo $\Delta(G)$: $$1 \le \chi(G) \le n$$ $$\chi(G) \le \Delta(G) + 1 \quad \text{(Cota Voraz)}$$

Cotas Estructurales Sea $\omega(G)$ el número de clan (el tamaño de la subgráfica completa más grande) y $\alpha(G)$ el número de independencia (el tamaño del conjunto más grande de vértices que no son adyacentes). $$\chi(G) \ge \omega(G)$$ $$\chi(G) \ge \frac{n}{\alpha(G)}$$

Clases de Gráficas Específicas

• Gráficas Completas ($K_n$): $\chi(K_n) = n$
• Gráficas Bipartitas: $\chi(G) \le 2$ si y solo si $G$ no tiene ciclos impares.
• Gráficas Ciclo ($C_n$): $$ \chi(C_n) = \begin{cases} 2 & \text{si } n \text{ es par} \ 3 & \text{si } n \text{ es impar} \end{cases} $$
• Gráficas Planares: $\chi(G) \le 4$ (El Teorema de los Cuatro Colores).

Teorema de Brooks Para cualquier gráfica conexa $G$ que no sea ni una gráfica completa ni un ciclo impar: $$\chi(G) \le \Delta(G)$$

Demostración

Teorema: Para cualquier gráfica $G$, el número cromático cumple que $\chi(G) \le \Delta(G) + 1$.

Demostración: La idea es demostrar este resultado usando el "Algoritmo Voraz de Coloración". Esta es una demostración constructiva que muestra que existe una coloración válida usando a lo más $\Delta(G) + 1$ colores.

Toma un orden arbitrario de los vértices de $G$, digamos $V(G) = {v_1, v_2, \dots, v_n}$. Deja que los colores disponibles sean el conjunto de enteros positivos ${1, 2, 3, \dots}$.

Asigna colores a los vértices uno por uno, de $v_1$ hasta $v_n$, siguiendo esta regla: asígnale a $v_i$ el entero positivo (color) más pequeño que no se le haya asignado ya a ninguno de sus vecinos en el conjunto ${v_1, \dots, v_{i-1}}$.

Fíjate en el paso donde estás coloreando el vértice $v_i$:

1. Sea $N(v_i)$ el conjunto de vecinos de $v_i$.
2. El número de vecinos de $v_i$ es su grado, que escribes como $d(v_i)$. Por definición, $d(v_i) \le \Delta(G)$.
3. Al considerar $v_i$, solo te importan los vecinos que ya fueron coloreados. Sea $k$ el número de vecinos de $v_i$ que aparecen antes en el orden (con índices del $1$ al $i-1$). Claramente, $k \le d(v_i) \le \Delta(G)$.
4. Estos $k$ vecinos usan, a lo mucho, $k$ colores distintos.
5. Como hay a lo más $\Delta(G)$ colores prohibidos, y tienes acceso al conjunto de colores ${1, 2, \dots, \Delta(G) + 1}$, debe haber al menos un color en este conjunto que no esté siendo usado por ningún vecino de $v_i$.
6. Específicamente, el color más pequeño disponible tiene que ser menor o igual a $k + 1$, lo cual es menor o igual a $\Delta(G) + 1$.

Como esta lógica funciona para cada vértice $v_i$ desde $i=1$ hasta $n$, el algoritmo logra colorear toda la gráfica usando colores del conjunto ${1, \dots, \Delta(G) + 1}$. Por lo tanto, existe una coloración propia con a lo más $\Delta(G) + 1$ colores.

$$\chi(G) \le \Delta(G) + 1$$ $\square$