Coloración de Aristas

Teoría

La coloración de aristas es un concepto fundamental en la teoría de gráficas donde asignas colores a las aristas de una gráfica $G$ de tal forma que no haya dos aristas adyacentes (aristas que comparten un vértice común) con el mismo color. A esto lo conocemos formalmente como una coloración propia de aristas. El objetivo principal es encontrar el número mínimo de colores necesarios para lograr una coloración propia de aristas para una gráfica $G$ dada. A este número mínimo lo llamamos índice cromático o número cromático de aristas, y lo denotamos como $\chi'(G)$. Este concepto es diferente a la coloración de vértices, ya que lo que hace es partir el conjunto de aristas de una gráfica en emparejamientos (matchings) independientes.

Estudiar la coloración de aristas es crucial en la optimización combinatoria y tiene aplicaciones directas en problemas de calendarización. Por ejemplo, si los vértices representan equipos en una liga deportiva y las aristas representan los juegos que deben jugar, $\chi'(G)$ representa el número mínimo de rondas necesarias para programar el torneo de modo que ningún equipo juegue más de un partido por ronda. En el contexto de las olimpiadas de matemáticas (AIME/USAMO), los problemas de coloración de aristas suelen aparecer como problemas de torneos "Round Robin" o acertijos en cuadrículas que puedes modelar como gráficas bipartitas.

Una intuición clave en la coloración de aristas es la relación entre el índice cromático y el grado máximo de la gráfica, denotado como $\Delta(G)$. Como todas las aristas que inciden en un solo vértice deben tener colores distintos, es trivial que $\chi'(G) \ge \Delta(G)$. El resultado más profundo en este campo, el Teorema de Vizing, dice que la cota superior es sorprendentemente ajustada: nunca necesitas más de $\Delta(G) + 1$ colores. Así que, para cualquier gráfica simple, el índice cromático solo puede tomar uno de dos valores posibles: $\Delta(G)$ o $\Delta(G) + 1$.

Fórmulas Clave

1. El Índice Cromático Para una gráfica $G$, el índice cromático $\chi'(G)$ cumple con la cota inferior trivial: $$ \chi'(G) \ge \Delta(G) $$ donde $\Delta(G)$ es el grado máximo de cualquier vértice en $G$.

2. Teorema de Vizing Para cualquier gráfica simple $G$, el índice cromático está acotado por: $$ \Delta(G) \le \chi'(G) \le \Delta(G) + 1 $$ A las gráficas donde $\chi'(G) = \Delta(G)$ las llamamos de Clase 1, y a las gráficas donde $\chi'(G) = \Delta(G) + 1$ las llamamos de Clase 2.

3. Teorema de Coloración de Líneas de König Toda gráfica bipartita $G$ es de Clase 1. Es decir: $$ \text{Si } G \text{ es bipartita, entonces } \chi'(G) = \Delta(G) $$

4. Gráficas Completas ($K_n$) El índice cromático de las gráficas completas depende de la paridad del número de vértices $n$: $$ \chi'(K_n) = \begin{cases} n-1 & \text{if } n \text{ es par} \ n & \text{if } n \text{ es impar} \end{cases} $$

5. Teorema de Shannon (Multigráficas) Para una multigráfica $G$ (donde se permiten varias aristas entre vértices), la cota es más amplia: $$ \chi'(G) \le \frac{3}{2}\Delta(G) $$

Demostración

Teorema: Teorema de Vizing Para cualquier gráfica simple $G$, $\chi'(G) \le \Delta(G) + 1$.

Demostración: Vamos a proceder por inducción sobre el número de aristas $m = |E(G)|$. Sea $k = \Delta(G) + 1$. Lo que queremos mostrar es que $G$ es $k$-arista-colorable.

Caso Base: Si $m=1$, la gráfica es trivialmente 1-colorable, y $1 \le \Delta(G) + 1$.

Paso Inductivo: Supón que para cualquier gráfica con $m$ aristas, el teorema se cumple. Considera una gráfica $G$ con $m+1$ aristas. Sea $xy_0$ una arista en $G$. Por la hipótesis de inducción, la gráfica $G - {xy_0}$ tiene una coloración propia de aristas con $k$ colores. Intentaremos colorear $xy_0$ para completar la coloración de $G$.

Definiciones:

1. Color Faltante: Para cualquier vértice $v$, sea $d(v)$ su grado. Como $d(v) \le \Delta(G) < k$, hay al menos un color del conjunto ${1, \dots, k}$ que no se usa en ninguna arista que incida en $v$. Denotamos como $M(v)$ al conjunto de colores faltantes en el vértice $v$.
2. Cadena de Kempe: Considera dos colores $\alpha$ y $\beta$. La subgráfica inducida por las aristas coloreadas con $\alpha$ o $\beta$ consiste en trayectorias y ciclos ajenos. A una trayectoria en esta subgráfica la llamamos cadena de Kempe $(\alpha, \beta)$. Podemos intercambiar los colores $\alpha$ y $\beta$ a lo largo de dicha componente sin invalidar la coloración propia en el resto de la gráfica.

Construcción del Abanico: Queremos colorear $xy_0$. Sea $c_0 \in M(y_0)$. Si $c_0 \in M(x)$, podemos colorear $xy_0$ con $c_0$ y ya terminamos. Supón que $c_0 \notin M(x)$. Entonces hay una arista $xy_1$ coloreada con $c_0$. Sea $c_1 \in M(y_1)$. Si $c_1 \in M(x)$, podemos "desplazar" el color: colorea $xy_1$ con $c_1$ y $xy_0$ con $c_0$. Si $c_1 \notin M(x)$, hay una arista $xy_2$ coloreada con $c_1$. Repetimos este proceso para construir una sucesión de vértices distintos $y_0, y_1, \dots, y_j$ y colores $c_0, c_1, \dots, c_{j-1}$ tales que la arista $xy_{i+1}$ tiene el color $c_i$ y $c_i \in M(y_i)$. A esta sucesión la llamamos Abanico de Vizing centrado en $x$.

Como la gráfica es finita, esta sucesión debe detenerse en algún momento. Sea $y_0, \dots, y_L$ el abanico maximal. Sea $c_L \in M(y_L)$.

Resolviendo el Conflicto: Hay dos casos respecto al color faltante $c_L$ del último vértice del abanico:

Caso 1: $c_L \in M(x)$. Podemos realizar un desplazamiento cíclico en el abanico. Recoloreamos $xy_i$ con $c_i$ para $i=0, \dots, L-1$, y finalmente coloreamos $xy_L$ con $c_L$. Como $c_L$ faltaba en $x$ y en $y_L$, esto es válido.

Caso 2: $c_L \notin M(x)$. Como el abanico es maximal pero no pudimos extenderlo, el color $c_L$ ya debe aparecer en la sucesión de colores $c_0, \dots, c_{L-1}$. Sea $c_L = c_k$ para algún $0 \le k < L-1$. Sea $\beta \in M(x)$. Por construcción, $\beta$ es diferente de todos los $c_i$ usados en las aristas del abanico que inciden en $x$. Considera la cadena de Kempe $(c_L, \beta)$ que empieza en $y_L$.

1. Si esta cadena no llega a $y_k$, podemos intercambiar los colores $c_L$ y $\beta$ a lo largo de la cadena conectada a $y_L$. Ahora $\beta \in M(y_L)$. Como $\beta \in M(x)$, estamos ahora en el Caso 1 (respecto al abanico truncado o extendido hasta $y_L$ con el color faltante $\beta$), y podemos desplazar los colores para terminar.
2. Si la cadena sí llega a $y_k$, entonces $y_k$ está conectado a $y_L$ mediante una trayectoria de colores alternados $c_L$ y $\beta$. Sin embargo, $y_k$ ya tiene el color faltante $c_k = c_L$. Esto implica que $y_k$ no puede ser un extremo de un segmento de trayectoria coloreado con $c_L$, lo cual es una contradicción (o implica que la estructura de la cadena permite un intercambio en $y_k$ que libera un color). Corrección por rigor: Específicamente, si la cadena $(c_L, \beta)$ conecta a $y_L$ y $y_k$, intercambiamos los colores en la cadena $(c_L, \beta)$ que empieza en $y_k$. Esto cambia $M(y_k)$ de $c_L$ a $\beta$.