Problemas de coloración en el plano

Regiones creadas por rectas en el plano

Cuando se trazan $n$ rectas en el plano general (sin dos paralelas y sin tres concurrentes), dividen el plano en regiones. ¿Cuántas regiones hay? La fórmula es $R(n) = 1 + n + \binom{n}{2} = \frac{n^2 + n + 2}{2}$.

Demostración por inducción: $R(0) = 1$ (el plano sin rectas es una sola región). Al agregar la $(n+1)$-ésima recta, intersecta a las $n$ rectas anteriores en $n$ puntos distintos, dividiendo la nueva recta en $n+1$ segmentos. Cada segmento divide una región existente en dos, añadiendo $n+1$ regiones. Luego $R(n+1) = R(n) + (n+1)$, con solución $R(n) = 1 + \sum_{k=1}^{n} k = 1 + \frac{n(n+1)}{2}$.

¿Con cuántos colores se pueden colorear las regiones de modo que dos regiones adyacentes (con un segmento de frontera en común, no solo un punto) tengan colores distintos?

La respuesta sorprendente es que siempre bastan 2 colores. Esto se debe a que el mapa de regiones creado por $n$ rectas en posición general es un grafo planar bipartito. La bipartición se construye así: coloreamos de blanco una región si está del "mismo lado" que la región original (el número de rectas que la separan de la región original es par) y de negro si está al otro lado (número impar de rectas cruzadas). Dos regiones adyacentes difieren en exactamente una recta cruzada, así que uno es par y el otro impar — bipartición perfecta.

Este resultado es especialmente elegante porque funciona para cualquier $n$ y cualquier arreglo de rectas (incluso con paralelas o concurrencias), siempre que se use la coloración de paridad adecuada.

El teorema de los 4 colores y argumentos elementales

El teorema de los 4 colores (Appel y Haken, 1976) afirma que todo mapa plano puede colorearse con a lo sumo 4 colores de modo que regiones adyacentes tengan colores distintos. La demostración original, asistida por computadora, es uno de los teoremas más famosos y polémicos de la matemática moderna.

Para olimpiadas, la versión útil del teorema es mucho más modesta: el teorema de los 5 colores (Heawood, 1890), que tiene una demostración puramente combinatoria. Pero en la práctica, los problemas olímpicos que involucran coloración de grafos planares suelen requerir argumentos más elementales.

Argumento elemental de planaridad: Todo grafo planar tiene un vértice de grado $\leq 5$ (corolario de la fórmula de Euler $V - E + F = 2$ y la cota $E \leq 3V - 6$). Por inducción (borrar el vértice de grado $\leq 5$, colorear el resto con 6 colores, y colorear el vértice eliminado con el color sobrante), todo grafo planar es 6-coloreable.

Argumento de 2-coloración (bipartición): Un mapa es 2-coloreable si y solo si su grafo dual es bipartito, lo que equivale a que todas las caras tengan longitud par. Para arreglos de rectas, todos los "ciclos" del grafo dual son pares (dos regiones separadas por una recta comparten toda la recta como frontera, creando una cara de longitud 2), de ahí la 2-coloración.

Coloración de grafos en olimpiadas: Los problemas olímpicos de coloración geométrica raramente necesitan el teorema de los 4 colores completo. Lo que sí aparece frecuentemente es: (a) demostrar que cierta configuración requiere exactamente $k$ colores; (b) construir una coloración válida con $k$ colores; (c) demostrar que $k-1$ colores no son suficientes.

Coloración de cuadrículas con restricciones

Los problemas de coloración de tableros y cuadrículas son abundantes en olimpiadas. La cuadrícula $m \times n$ como grafo (vértices = celdas, aristas = celdas adyacentes horizontal o verticalmente) es bipartita (la coloración de ajedrez lo certifica), luego es 2-coloreable.

Coloración con restricciones adicionales: Si se pide que cada color aparezca exactamente $k$ veces, o que ninguna fila tenga dos celdas del mismo color, o que la coloración sea "balanceada", se necesitan técnicas de conteo y matchings.

**Ejemplo — Coloración con 3 colores en $3 \times 3$:** ¿De cuántas maneras se puede colorear un tablero $3 \times 3$ con 3 colores de modo que en cada fila y cada columna aparezcan los 3 colores exactamente una vez? Esto equivale a contar los cuadrados latinos de orden 3. Hay $12$ cuadrados latinos de orden 3 (fijando la primera fila como $123$, hay 4 maneras de completar el resto; con $3! = 6$ permutaciones de los 3 colores en la primera fila, hay $6 \times 2 = 12$ cuadrados latinos — de hecho hay exactamente 12 de orden 3 módulo permutaciones de la primera fila, y $12$ en total sin reducir).

Coloración de una cuadrícula con restricciones de distancia: Coloreamos los vértices de $\mathbb{Z}^2$ con $k$ colores de modo que dos vértices a distancia 1 (en la métrica euclidiana o de Manhattan) tengan colores distintos. Para la distancia Manhattan, bastan 2 colores (la 2-coloración de ajedrez). Para la distancia euclidiana (incluyendo vecinos en diagonal), se necesitan 4 colores (los vértices forman el grafo rey $K_4$-free).

Tip olímpico: Cuando el problema pide colorear una estructura geométrica con restricciones, lo primero es identificar el grafo subyacente (qué pares de objetos son "adyacentes") y luego aplicar los teoremas de coloración de grafos.

Coloración de grafos y número cromático en contextos geométricos

El número cromático $\chi(G)$ de un grafo $G$ es el mínimo número de colores necesarios para una coloración propia. Calcular $\chi(G)$ en general es un problema NP-difícil, pero para familias geométricas específicas hay cotas y fórmulas exactas.

Grafos de intervalos: Si los vértices son intervalos en la recta real y dos son adyacentes si se solapan, el número cromático es igual al número de solapamiento máximo (la "densidad" del conjunto de intervalos). Este resultado tiene aplicaciones en problemas de asignación de frecuencias o turnos.

Grafos de discos: Si los vértices son discos en el plano y dos son adyacentes si se intersectan, $\chi(G)$ puede ser arbitrariamente grande. Sin embargo, si todos los discos tienen el mismo radio, $\chi(G) \leq 5$ (argumento geométrico: cada disco intersecta a lo sumo $\pi / \arcsin(1/2) - 1 = 5$ discos del mismo tamaño que lo rodean sin solapar sus centros).

Grafos de Kneser: El grafo de Kneser $KG(n,k)$ tiene como vértices los subconjuntos de $k$ elementos de $[n]$, con dos subconjuntos adyacentes si son disjuntos. El teorema de Lovász (1978) afirma que $\chi(KG(n,k)) = n - 2k + 2$. La demostración usa métodos topológicos y fue uno de los primeros usos de la cohomología en combinatoria. Para olimpiadas, el caso $KG(n,2)$ (el grafo de Petersen generalizado) es el más relevante.

Coloración de grafos de intersección: En general, para grafos de intersección de segmentos, triángulos, o polígonos convexos en el plano, el número cromático puede ser mayor que el número de clique ($\omega(G)$). Los grafos para los que $\chi(G) = \omega(G)$ siempre se cumplen se llaman grafos perfectos (teorema de los grafos perfectos fuertes: Chudnovsky et al., 2006).

Problema trabajado: coloración en un problema IbAm

Problema (estilo IbAm): Se pintan algunos segmentos del plano de modo que cada punto del plano pertenece a lo sumo a 2 segmentos. Se dice que dos segmentos son "rivales" si se intersectan en un punto interior de ambos. Demuestra que los segmentos pueden colorearse con 3 colores de modo que dos segmentos rivales tengan colores distintos.

Solución: Construimos el grafo de intersección $G$: los vértices son los segmentos y hay una arista entre dos segmentos si son rivales (se cruzan en un punto interior). Debemos demostrar que $\chi(G) \leq 3$.

Clave estructural: Como cada punto del plano pertenece a lo sumo a 2 segmentos, cada punto de intersección involucra exactamente 2 segmentos. Esto significa que el grafo $G$ no contiene $K_4$ como subgrafo (pues $K_4$ requeriría 4 segmentos mutuamente cruzados, y por el teorema de Radon en dimensión 1 no es posible que 4 segmentos se crucen mutuamente en el plano con intersecciones simples). En realidad, el grafo $G$ es planar: se puede dibujar en el plano de modo que las aristas no se crucen (identificando cada vértice con el segmento y trazando aristas curvas que siguen los cruces reales).

Aplicación del teorema de los 4 colores (o 5 colores elementales): Como $G$ es planar, por el teorema de los 4 colores $\chi(G) \leq 4$. ¿Podemos mejorar a 3? Sí: el grafo $G$ en este contexto específico es un grafo de intersección de segmentos con cada punto de intersección de multiplicidad 2, lo que hace que $G$ tenga un número par de caras (por la estructura del arreglo), y por el teorema de Grötzsch (todo grafo planar sin triángulos es 3-coloreable), si $G$ no tiene triángulos bastan 3 colores. Sin triángulos en $G$ significa que no hay tres segmentos que se corten mutuamente — hipótesis que puede necesitarse explícita. Con la hipótesis adicional de ausencia de triángulos, $\chi(G) \leq 3$. $\square$

Reflexión: Este problema ilustra el patrón "grafo geométrico + teorema de coloración de grafos planares". La habilidad clave es modelar la configuración geométrica como un grafo y luego aplicar el teorema correcto.

Cuántos colores necesitan los mapas en superficies

La generalización del problema de los 4 colores a otras superficies usa la fórmula de Heawood: para una superficie de característica de Euler $\chi_E$, el número cromático es a lo sumo $\left\lfloor \frac{7 + \sqrt{49 - 24\chi_E}}{2} \right\rfloor$.

Para la esfera ($\chi_E = 2$): $\lfloor (7 + 1)/2 \rfloor = 4$ colores — este es el teorema de los 4 colores.

Para el toro ($\chi_E = 0$): $\lfloor (7 + 7)/2 \rfloor = 7$ colores. La cota de 7 colores para el toro es exacta y se puede alcanzar con el grafo de Heawood $K_7$, que se embebe en el toro.

Para el plano proyectivo real ($\chi_E = 1$): $\lfloor (7 + 5)/2 \rfloor = 6$ colores.

Estos resultados son de nivel olímpico avanzado, pero ilustran cómo la topología y la combinatoria se interconectan. En competencias IbAm/Cono Sur el foco está en argumentos elementales de grafos planares, no en topología algebraica.

Para recordar en olimpiadas: (a) Arreglo de rectas: 2 colores; (b) Mapa planar general: 4 colores (teorema profundo), 5 colores (demostración elemental); (c) Mapa en el toro: 7 colores. La 2-coloración de arreglos de rectas es el resultado más útil y tiene demostración directa por paridad.