Coloraciones y el Teorema de los 4 Colores

El problema del mapa

Imagina que debes colorear un mapa de países de modo que países fronterizos (que comparten una arista, no solo un punto) tengan colores distintos. ¿Cuántos colores necesitas? Esta pregunta, planteada a mediados del siglo XIX, llevó a uno de los teoremas más famosos de la matemática.

Traducida al lenguaje de grafos: cada país es un vértice y dos países son adyacentes si comparten frontera. Colorear el mapa equivale a colorear los vértices del grafo con la condición de que vértices adyacentes tengan colores distintos.

Coloración propia y número cromático

Una coloración propia de $G = (V,E)$ con $k$ colores es una función $c: V \to \{1, 2, \ldots, k\}$ tal que $c(u) \ne c(v)$ siempre que $\{u,v\} \in E$.

El número cromático $\chi(G)$ es el menor $k$ para el cual existe una coloración propia con $k$ colores.

Ejemplos básicos:

$\chi(K_n) = n$: en el grafo completo, todos los vértices son adyacentes entre sí, así que necesitamos un color distinto para cada uno.

$\chi(C_n) = 2$ si $n$ es par, $\chi(C_n) = 3$ si $n$ es impar: en un ciclo par podemos alternar dos colores; en un ciclo impar, al volver al inicio los dos colores entran en conflicto y se necesita un tercero.

$\chi(G) = 1$ si y solo si $G$ no tiene aristas ($G$ es el grafo vacío). $\chi(G) = 2$ si y solo si $G$ es bipartito (con al menos una arista).

Coloraciones de grafos bipartitos

Teorema: Un grafo (con al menos una arista) es bipartito si y solo si $\chi(G) = 2$, lo que equivale a no tener ciclos impares.

Demostración de la necesidad: si $G$ es bipartito con partes $A$ y $B$, coloreamos $A$ con el color 1 y $B$ con el color 2. Como toda arista va de $A$ a $B$, extremos de distinto color: es una coloración propia con 2 colores.

Demostración de la suficiencia: si $\chi(G) = 2$, sea $c$ una coloración propia con colores 1 y 2. Poner $A = c^{-1}(1)$ y $B = c^{-1}(2)$: toda arista conecta vértices de distinto color, luego toda arista va de $A$ a $B$, y $G$ es bipartito.

Para detectar si un grafo es bipartito: recorre el grafo en anchura (BFS) coloreando alternadamente. Si en algún momento dos vértices adyacentes reciben el mismo color, el grafo no es bipartito (contiene un ciclo impar).

Cota de Brooks y grafos planares

Una cota sencilla: $\chi(G) \le \Delta(G) + 1$, donde $\Delta(G)$ es el grado máximo de $G$. Esto se demuestra fácilmente con un algoritmo voraz: colorea los vértices uno a uno; al colorear $v$, como tiene a lo sumo $\Delta(G)$ vecinos ya coloreados, siempre queda al menos un color disponible entre los $\Delta(G) + 1$ colores.

Un grafo planar es uno que puede dibujarse en el plano sin que las aristas se crucen. Los mapas geográficos corresponden a grafos planares.

El Teorema de los 5 Colores (demostrado en 1890) afirma que todo grafo planar satisface $\chi(G) \le 5$. Su demostración es accesible a nivel olímpico y usa el hecho de que todo grafo planar tiene un vértice de grado $\le 5$.

El Teorema de los 4 Colores (Appel y Haken, 1976) afirma que $\chi(G) \le 4$ para todo grafo planar. Su demostración involucra verificación por computadora de cientos de casos y está fuera del alcance olímpico, pero el enunciado se usa libremente en competencias.

Estrategia para problemas de coloración en olimpiadas

Los problemas de coloración en la ONEM regional suelen pedir: (a) demostrar que cierta coloración existe dando $k$ colores explícitamente, (b) demostrar que menos de $k$ colores no alcanzan exhibiendo un subgrafo que los requiere, o (c) contar el número de coloraciones propias con exactamente $k$ colores.

Para (a), los algoritmos voraces o las construcciones periódicas son suficientes. Para (b), identificar un subgrafo completo $K_k$ o un ciclo impar es la estrategia más común.

Para (c), el polinomio cromático $P(G, k)$ cuenta el número de coloraciones propias con exactamente $k$ colores asignados de un conjunto de $k$ colores. Por ejemplo, $P(K_3, k) = k(k-1)(k-2)$ y $P(C_4, k) = (k-1)^4 + (k-1)$. El cálculo de polinomios cromáticos aparece ocasionalmente en competencias regionales avanzadas.

Regla práctica: si el grafo es bipartito, 2 colores; si contiene un triángulo ($K_3$), al menos 3 colores; si es planar, a lo sumo 4 colores.