Coloracion de Grafos
Cuantos colores necesita cada grafo platonico? El Teorema de los 4 Colores establece el limite.
1. Coloracion de Vertices
Una \(k\)-coloracion propia de un grafo \(G = (V, E)\) es una funcion \(c: V \to \{1, 2, \ldots, k\}\) tal que si \(\{u, v\} \in E\) entonces \(c(u) \neq c(v)\). En otras palabras, asigna \(k\) colores a los vertices de modo que vertices adyacentes reciban colores distintos.
El numero cromatico \(\chi(G)\) es el minimo valor de \(k\) para el cual existe una \(k\)-coloracion propia:
$$ \chi(G) = \min\{k : G \text{ admits a proper } k\text{-coloring}\} $$Determinar \(\chi(G)\) es en general un problema NP-dificil, pero existen cotas utiles. Como cota inferior, el numero de clique \(\omega(G)\) (tamano del mayor subgrafo completo) satisface \(\chi(G) \geq \omega(G)\), porque los vertices de una clique necesitan todos colores distintos. Tambien se tiene \(\chi(G) \geq |V| / \alpha(G)\), donde \(\alpha(G)\) es el numero de independencia (tamano del mayor conjunto independiente).
Como cota superior, el algoritmo greedy garantiza \(\chi(G) \leq \Delta(G) + 1\), donde \(\Delta(G)\) es el grado maximo. En la practica, la mayoria de grafos admiten coloraciones mucho mejores que esta cota.
2. Numeros Cromaticos de los Cinco Solidos
Tetraedro: \(\chi = 4\). El grafo del tetraedro es \(K_4\), el grafo completo de 4 vertices. Como todo par de vertices es adyacente, cada vertice necesita un color distinto. Para cualquier grafo completo:
$$ \chi(K_n) = n $$Cubo: \(\chi = 2\). El grafo del cubo es \(Q_3\), el hipercubo de dimension 3. Es bipartito: los vertices con un numero par de 1-bits en su representacion binaria forman una parte, y los de numero impar la otra. Toda arista conecta vertices que difieren en exactamente un bit, asi que cambian de paridad. Un grafo es 2-coloreable si y solo si es bipartito:
$$ \chi(G) = 2 \iff G \text{ es bipartito} \iff G \text{ no tiene ciclos impares} $$Octaedro: \(\chi = 3\). El grafo del octaedro es \(K_{2,2,2}\), el grafo tripartito completo. Cada vertice es adyacente a todos los demas excepto a su vertice antipodal. Contiene triangulos (por ejemplo, los vertices 0, 1, 2 son mutuamente adyacentes), por lo que no es bipartito y \(\chi \geq 3\). La 3-coloracion optima asigna el mismo color a cada par antipodal: color A a \(\{0, 5\}\), color B a \(\{1, 3\}\), color C a \(\{2, 4\}\). Verificacion: el vertice 0 es adyacente a 1, 2, 3, 4 con colores B, C, B, C, todos distintos de A. El vertice 5 es adyacente a 1, 2, 3, 4 con los mismos colores, todos distintos de A.
Dodecaedro: \(\chi = 3\). El dodecaedro no es bipartito porque contiene pentagonos (ciclos de longitud 5, que son impares), asi que \(\chi \geq 3\). Se puede construir explicitamente una 3-coloracion valida para sus 20 vertices. Como no contiene \(K_4\) como subgrafo (es 3-regular, asi que \(\omega \leq 3\)), la cota inferior \(\omega = 3\) coincide con la cota superior.
Icosaedro: \(\chi = 4\). El icosaedro contiene \(K_4\) como subgrafo: por ejemplo, el vertice 0 es adyacente a 1, y ambos son adyacentes a 2 y a 5, pero ademas 2 y 5 no son adyacentes entre si. Sin embargo, tomando los vertices 0, 1, 2, 6 se verifica que todos son mutuamente adyacentes, formando un \(K_4\). Esto da \(\chi \geq 4\). Por el Teorema de los 4 Colores (todo grafo planar es 4-coloreable) se tiene \(\chi \leq 4\). Luego \(\chi = 4\).
| Solido | Grafo | V | \(\Delta\) | \(\omega\) | \(\chi\) | Razon |
|---|---|---|---|---|---|---|
| Tetraedro | \(K_4\) | 4 | 3 | 4 | 4 | Completo |
| Cubo | \(Q_3\) | 8 | 3 | 2 | 2 | Bipartito |
| Octaedro | \(K_{2,2,2}\) | 6 | 4 | 3 | 3 | Tripartito completo |
| Dodecaedro | 3-reg | 20 | 3 | 3 | 3 | Ciclos impares, 3-col. |
| Icosaedro | 5-reg | 12 | 5 | 4 | 4 | Contiene \(K_4\), planar |
Los cinco grafos platonicos con coloracion optima de vertices
3. Algoritmo Greedy y Teorema de Brooks
El algoritmo greedy de coloracion funciona asi: se fija un orden \(v_1, v_2, \ldots, v_n\) de los vertices y, para cada vertice \(v_i\), se le asigna el menor color positivo que no este usado por ninguno de sus vecinos ya coloreados. Como \(v_i\) tiene a lo sumo \(\Delta(G)\) vecinos, y cada uno usa a lo sumo un color, siempre hay un color disponible entre \(\{1, 2, \ldots, \Delta(G) + 1\}\). Esto demuestra:
$$ \chi(G) \leq \Delta(G) + 1 $$El teorema de Brooks (1941) mejora esta cota: si \(G\) es conexo y no es un grafo completo ni un ciclo impar, entonces \(\chi(G) \leq \Delta(G)\).
$$ \chi(G) \leq \Delta(G) \quad \text{(Brooks, salvo } G = K_n \text{ o } G = C_{2k+1}\text{)} $$Aplicado a los grafos platonicos: el tetraedro es \(K_4\), asi que es una excepcion de Brooks y efectivamente \(\chi = \Delta + 1 = 4\). Los demas satisfacen la cota de Brooks: el cubo tiene \(\chi = 2 \leq 3 = \Delta\), el octaedro \(\chi = 3 \leq 4 = \Delta\), el dodecaedro \(\chi = 3 = \Delta\) y el icosaedro \(\chi = 4 \leq 5 = \Delta\).
Notar que el dodecaedro alcanza la cota de Brooks con igualdad (\(\chi = \Delta = 3\)), mientras que el cubo y el octaedro quedan estrictamente por debajo.
4. Teorema de los Cuatro Colores
En 1852, Francis Guthrie observo que para colorear un mapa de los condados de Inglaterra bastaban 4 colores y conjeturo que esto era cierto para todo mapa. La conjetura paso por una "demostracion" incorrecta de Kempe (1879), cuyo error fue descubierto por Heawood (1890). Heawood salvo lo que pudo y demostro el teorema de los 5 colores: todo grafo planar satisface \(\chi(G) \leq 5\).
La demostracion completa del teorema de los 4 colores llego en 1976, cuando Appel y Haken usaron un ordenador para verificar 1,936 configuraciones reducibles. Fue la primera demostracion matematica importante asistida por computadora:
$$ \text{G planar} \implies \chi(G) \leq 4 $$El tetraedro (\(K_4\)) muestra que la cota 4 es optima: es un grafo planar con \(\chi = 4\). El icosaedro es otro ejemplo que alcanza la cota. De los cinco solidos platonicos, dos requieren exactamente 4 colores, dos requieren 3 y uno requiere solo 2.
Para referencia, el teorema de los 5 colores es mucho mas facil de demostrar: se usa induccion sobre \(|V|\) junto con la formula de Euler (\(|E| \leq 3|V| - 6\) para grafos planares), que garantiza la existencia de un vertice de grado \(\leq 5\).
5. El Polinomio Cromatico
El polinomio cromatico \(P(G, k)\) cuenta el numero de \(k\)-coloraciones propias de \(G\). Es un polinomio en \(k\) de grado \(|V|\), y codifica informacion combinatoria profunda sobre el grafo.
Se calcula mediante eliminacion-contraccion: dada una arista \(e = \{u,v\}\), se define \(G - e\) como el grafo sin la arista \(e\) y \(G/e\) como el grafo donde se contraen \(u\) y \(v\) en un solo vertice. Entonces:
$$ P(G, k) = P(G - e, k) - P(G / e, k) $$Ejemplos fundamentales. Para el grafo completo \(K_n\): el primer vertice tiene \(k\) opciones, el segundo \(k-1\) (distinto del primero), el tercero \(k-2\), y asi sucesivamente:
$$ P(K_n, k) = k(k-1)(k-2)\cdots(k-n+1) = k^{\underline{n}} $$Para un camino \(P_n\) de \(n\) vertices: el primer vertice tiene \(k\) opciones, y cada siguiente tiene \(k-1\) (solo debe diferir de su predecesor):
$$ P(P_n, k) = k(k-1)^{n-1} $$Para un ciclo \(C_n\):
$$ P(C_n, k) = (k-1)^n + (-1)^n(k-1) $$Para el tetraedro \(K_4\): \(P(K_4, k) = k(k-1)(k-2)(k-3)\). Con 4 colores disponibles: \(P(K_4, 4) = 4 \cdot 3 \cdot 2 \cdot 1 = 24\) coloraciones propias. Esto coincide con \(4!\), las permutaciones de los 4 colores asignados a los 4 vertices.
Verificacion para \(C_3 = K_3\) (triangulo):
P(C_3, k) = (k-1)^3 + (-1)^3(k-1) = (k-1)^3 - (k-1) = (k-1)[(k-1)^2 - 1] = (k-1)(k-2)k = k(k-1)(k-2)
Coincide con P(K_3, k) = k(k-1)(k-2). Con k=3: P = 3*2*1 = 6 coloraciones.
6. Coloracion de Aristas
La coloracion de aristas asigna colores a las aristas de modo que aristas incidentes (que comparten un vertice) reciban colores distintos. El indice cromatico \(\chi'(G)\) es el minimo numero de colores necesarios.
El teorema de Vizing (1964) establece que \(\chi'(G)\) solo puede tomar uno de dos valores:
$$ \Delta(G) \leq \chi'(G) \leq \Delta(G) + 1 $$Los grafos con \(\chi' = \Delta\) se llaman de Clase 1, y los con \(\chi' = \Delta + 1\) de Clase 2. Los cinco grafos platonicos son todos de Clase 1:
| Solido | \(\Delta\) | \(\chi'\) | Clase |
|---|---|---|---|
| Tetraedro | 3 | 3 | 1 |
| Cubo | 3 | 3 | 1 |
| Octaedro | 4 | 4 | 1 |
| Dodecaedro | 3 | 3 | 1 |
| Icosaedro | 5 | 5 | 1 |
Que todos sean de Clase 1 no es coincidencia: un resultado clasico establece que todo grafo planar con \(\Delta \geq 7\) es de Clase 1. Para grados menores, hay que verificar caso por caso, pero los grafos platonicos resultan ser todos de Clase 1.
Ejercicios
1. Verifica que el polinomio cromatico de \(K_3\) (triangulo) es \(P(K_3, k) = k(k-1)(k-2)\). Cuantas 3-coloraciones propias tiene? Cuantas 4-coloraciones?
2. Usa el metodo de eliminacion-contraccion para calcular \(P(C_4, k)\) para el 4-ciclo. Verifica la formula \(P(C_n, k) = (k-1)^n + (-1)^n(k-1)\) para \(n = 4\).
3. El cubo es bipartito. Demuestra que todo grafo bipartito \(G\) satisface \(P(G, k) \geq k(k-1)^{|V|-1}\), es decir, tiene al menos tantas coloraciones como un arbol con los mismos vertices.
4. Muestra que el icosaedro contiene \(K_4\) como subgrafo identificando 4 vertices mutuamente adyacentes. Concluye que \(\chi(\text{icosaedro}) \geq 4\).
5. Para el octaedro con \(\chi = 3\), exhibe todas las 3-coloraciones esencialmente distintas (salvo permutacion de colores). Cuantas 3-coloraciones propias \(P(\text{octaedro}, 3)\) hay en total?
LAB: Coloracion Interactiva de Grafos
Selecciona un grafo platonico y colorea sus vertices. Elige un color de la paleta y haz clic en un vertice para asignarlo. El panel muestra las violaciones de adyacencia.