Coloración de Grafos Bipartitos

Teoría

La coloración de grafos bipartitos es un concepto fundamental en la teoría de gráficas que describe grafos cuyos vértices puedes dividir en dos conjuntos disjuntos e independientes, $U$ y $V$. En un grafo así, cada arista conecta un vértice en $U$ con uno en $V$. Esta propiedad estructural es equivalente a que el grafo sea 2-coloreable: puedes asignar uno de dos colores (por ejemplo, blanco y negro) a cada vértice de tal forma que no haya dos vértices adyacentes con el mismo color. Si un grafo tiene al menos una arista, su número cromático es exactamente 2; si no tiene aristas, es 1.

Este concepto es clave en combinatoria porque te da una restricción de paridad muy estricta sobre la estructura del grafo. La utilidad más importante de la coloración bipartita en problemas de Olimpiada viene de su relación con los ciclos. Un grafo es bipartito si y solo si no contiene ciclos de longitud impar. Esto te permite demostrar que una configuración o coloración específica es imposible si encuentras un ciclo impar, o al revés, construir una coloración válida demostrando que no existen tales ciclos.

De forma intuitiva, puedes ver la coloración bipartita como un argumento de paridad. Si empiezas en un vértice y te mueves por las aristas, cada paso te lleva de un conjunto de la partición al otro. Para regresar al conjunto inicial, tienes que dar un número par de pasos. Por lo tanto, para volver al mismo vértice donde empezaste (completando un ciclo), la longitud total del camino debe ser par. Esta propiedad "alternante" es la idea clave para resolver problemas de tableros, coloración de mapas y alcanzabilidad en máquinas de estados.

Fórmulas Clave

Definición de un Grafo Bipartito Un grafo $G = (V, E)$ es bipartito si puedes partir $V$ en dos conjuntos disjuntos $A$ y $B$ tales que: $$V = A \cup B, \quad A \cap B = \emptyset$$ $$\forall (u, v) \in E, \quad (u \in A \land v \in B) \lor (u \in B \land v \in A)$$

Condición del Número Cromático El número cromático $\chi(G)$ cumple que: $$G \text{ es bipartito} \iff \chi(G) \le 2$$ (Nota: $\chi(G) = 2$ para cualquier grafo bipartito con al menos una arista).

Teorema de Kőnig (Caracterización mediante Ciclos) Un grafo $G$ es bipartito si y solo si no contiene ciclos impares. $$G \text{ es bipartito} \iff \text{longitud del ciclo } \equiv 0 \pmod 2 \text{ para todos los ciclos en } G$$

Teorema de Turán (Caso Bipartito) El número máximo de aristas en un grafo sin triángulos (y por lo tanto, potencialmente bipartito) con $n$ vértices es: $$|E| \le \left\lfloor \frac{n^2}{4} \right\rfloor$$ Este límite se alcanza con el grafo bipartito completo $K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$.

Demostración

Teorema: Un grafo $G$ es bipartito si y solo si no contiene ciclos impares.

Demostración:

Parte 1: $(\Rightarrow)$ Si $G$ es bipartito, no tiene ciclos impares. Supón que $G$ es bipartito. Por definición, puedes partir el conjunto de vértices $V$ en dos conjuntos disjuntos $A$ y $B$ de modo que cada arista conecte un vértice en $A$ con uno en $B$. Sea $v_1, v_2, \dots, v_k, v_1$ un ciclo de longitud $k$ en $G$. Sin perder generalidad, supón que $v_1 \in A$. Como $v_1$ es adyacente a $v_2$, entonces $v_2$ tiene que estar en $B$. Como $v_2$ es adyacente a $v_3$, entonces $v_3$ tiene que estar en $A$. Por inducción, para cualquier vértice $v_i$ en la secuencia: $$v_i \in A \text{ si } i \text{ es impar}$$ $$v_i \in B \text{ si } i \text{ es par}$$ Para que la arista $(v_k, v_1)$ exista, $v_k$ y $v_1$ deben estar en conjuntos diferentes. Como $v_1 \in A$, tenemos que $v_k \in B$. Siguiendo nuestro patrón, $v_k \in B$ implica que $k$ es par. Así que todo ciclo debe tener una longitud par.

Parte 2: $(\Leftarrow)$ Si $G$ no tiene ciclos impares, es bipartito. Supón que $G$ no tiene ciclos impares. Hay que mostrar que $G$ es 2-coloreable. Sin perder generalidad, supón que $G$ es conexo (si no lo es, aplicas esta misma lógica a cada componente conexa por separado).

1. Escoge un vértice arbitrario $v_0 \in V$.
2. Para cada vértice $v \in V$, sea $d(v_0, v)$ la longitud del camino más corto (geodésica) de $v_0$ a $v$.
3. Parte $V$ en los conjuntos $A$ y $B$ de la siguiente manera: $$A = {v \in V \mid d(v_0, v) \text{ es par}}$$ $$B = {v \in V \mid d(v_0, v) \text{ es impar}}$$

Lo que hay que demostrar es que no hay dos vértices adyacentes dentro del mismo conjunto.

Caso 1: Vértices en $A$. Supón que existen $u, w \in A$ tales que $(u, w) \in E$. Sean $P_u$ el camino más corto de $v_0$ a $u$, y $P_w$ el camino más corto de $v_0$ a $w$. Las longitudes $|P_u|$ y $|P_w|$ son ambas pares. La caminata que consiste en $P_u$ seguida de la arista $(u, w)$ y luego $P_w$ en reversa es una caminata cerrada de longitud $|P_u| + 1 + |P_w|$. Como $|P_u|$ y $|P_w|$ son pares, la longitud total es $\text{Par} + 1 + \text{Par} = \text{Impar}$. Una caminata cerrada de longitud impar debe contener un ciclo impar. Esto contradice la hipótesis de que $G$ no tiene ciclos impares. Por lo tanto, no existe tal arista $(u, w)$.

Caso 2: Vértices en $B$. Supón que existen $u, w \in B$ tales que $(u, w) \in E$. De la misma forma, $|P_u|$ y $|P_w|$ son ambos impares. La caminata cerrada tiene longitud $|P_u| + 1 + |P_w| = \text{Impar} + 1 + \text{Impar} = \text{Impar}$. Esto de nuevo implica que existe un ciclo impar, lo cual es una contradicción.

Como no hay aristas dentro de $A$ ni aristas dentro de $B$, todas las aristas deben conectar un vértice en $A$ con uno en $B$. Por lo tanto, $G$ es bipartito.

$\square$