Teorema de Brooks: cota del número cromático de un grafo

Teorema de Brooks: cota del número cromático de un grafo
Índice
  1. Conceptos básicos de coloración
  2. La cota fácil: Δ + 1 colores
  3. Enunciado del teorema de Brooks
  4. Ejemplos comprobados
  5. Idea de la demostración
  6. Aplicaciones
  7. Relación con otros resultados
  8. Preguntas frecuentes
    1. ¿Qué dice el teorema de Brooks?
    2. ¿Por qué los ciclos impares son una excepción?
    3. ¿Quién demostró el teorema de Brooks y cuándo?
    4. ¿El teorema de Brooks da el número cromático exacto?
  9. Fuentes

Actualizado el

El teorema de Brooks dice que los vértices de un grafo conexo se pueden colorear con tantos colores como su grado máximo Δ, de forma que dos vértices unidos nunca tengan el mismo color, con solo dos excepciones: los grafos completos y los ciclos de longitud impar, que necesitan Δ + 1. Mejora en una unidad la cota que da el método más simple de coloración y caracteriza exactamente cuándo esa unidad hace falta.

Conceptos básicos de coloración

  • Un grafo G está formado por vértices y aristas que unen pares de vértices. Aquí los grafos son simples (sin lazos ni aristas repetidas) y no dirigidos.
  • El grado de un vértice es el número de aristas que llegan a él, y Δ(G) es el grado máximo.
  • Una coloración propia asigna un color a cada vértice de modo que los extremos de cada arista tengan colores distintos. El número cromático χ(G) es el mínimo número de colores necesario.
  • Kn es el grafo completo de n vértices (todos unidos con todos) y Cn el ciclo de n vértices.

La cota fácil: Δ + 1 colores

Antes de Brooks hay un resultado sencillo: χ(G) ≤ Δ(G) + 1 para todo grafo. Se demuestra con la coloración voraz: se recorren los vértices en cualquier orden y a cada uno se le da el primer color que no use ninguno de sus vecinos ya coloreados. Como un vértice tiene como mucho Δ vecinos, entre Δ + 1 colores siempre queda uno libre.

Enunciado del teorema de Brooks

Sea G un grafo conexo con grado máximo Δ. Si G no es un grafo completo ni un ciclo impar, entonces

χ(G) ≤ Δ(G)

En los dos casos excluidos se tiene χ = Δ + 1: un grafo completo Kn tiene Δ = n − 1 y necesita n colores, porque todos sus vértices son vecinos entre sí; un ciclo impar tiene Δ = 2 y necesita 3 colores, porque al dar la vuelta con dos colores alternos el último vértice choca con el primero.

La condición de conexión no es una limitación real: si G no es conexo se aplica el teorema a cada componente por separado.

Ejemplos comprobados

Hemos calculado por fuerza bruta el número cromático de estos grafos para comprobar la tabla:

GrafoΔχ¿Qué dice Brooks?
K4 (completo, 4 vértices)34excepción: χ = Δ + 1
C5 (ciclo impar)23excepción: χ = Δ + 1
C6 (ciclo par)22χ ≤ 2, se alcanza
Grafo de Petersen (10 vértices, 15 aristas)33χ ≤ 3, se alcanza
Rueda W5 (ciclo de 5 más un centro)54χ ≤ 5, sobra uno
Cubo (8 vértices)32χ ≤ 3, sobra uno
Estrella K1,552χ ≤ 5, muy holgada

Los dos últimos casos muestran que Brooks es una cota superior y puede quedar lejos del valor real: un grafo bipartito siempre tiene χ ≤ 2, tenga el grado que tenga.

Ejemplo resuelto: la rueda W5. El centro está unido a los cinco vértices del ciclo, así que Δ = 5. No es completo (dos vértices del borde no consecutivos no están unidos) ni un ciclo, luego Brooks garantiza χ ≤ 5. Calculemos el valor exacto: el ciclo exterior C5 es impar y necesita 3 colores; el centro es vecino de todos ellos y necesita un cuarto. Por tanto χ(W5) = 4.

Ejemplo resuelto: el grafo de Petersen. Todos sus vértices tienen grado 3. Brooks da χ ≤ 3. Como contiene ciclos de 5 vértices, que son impares, no se puede colorear con 2. Así que χ = 3, y la cota de Brooks es exacta.

Idea de la demostración

R. Leonard Brooks publicó el teorema en 1941 en Proceedings of the Cambridge Philosophical Society. La prueba que suele enseñarse hoy es una simplificación de László Lovász, de 1975, basada en elegir bien el orden de la coloración voraz:

  1. Si algún vértice v tiene grado menor que Δ: se ordenan los vértices de más lejos a más cerca de v (por ejemplo, recorriendo un árbol generador hacia v). Cada vértice distinto de v tiene, en el momento de colorearlo, un vecino aún sin colorear (el siguiente en el camino hacia v), así que como mucho Δ − 1 vecinos coloreados. A v le llega con Δ colores porque su grado es menor que Δ.
  2. Si el grafo no es 2-conexo (tiene un vértice cuya eliminación lo desconecta): se colorea cada bloque por separado con Δ colores y se ajustan los colores en los vértices de corte permutándolos.
  3. El caso difícil: G 2-conexo, Δ-regular y Δ ≥ 3. Como G no es completo, hay un vértice v con dos vecinos x e y no unidos entre sí, y se puede elegir de modo que G − x − y siga siendo conexo. Se dan a x e y el mismo color, y se colorea el resto con el orden voraz que acaba en v. Cuando le toca a v, dos de sus Δ vecinos comparten color, así que usan como mucho Δ − 1 colores y queda uno libre.

El caso Δ = 2 corresponde a caminos y ciclos, donde el resultado se comprueba a mano: solo los ciclos impares necesitan 3 colores.

Aplicaciones

  • Calendarios de exámenes. Cada asignatura es un vértice y dos se unen si comparten alumnos. Un color es una franja horaria. Si ninguna asignatura choca con más de 6 otras y el grafo no es completo, bastan 6 franjas.
  • Asignación de frecuencias. Antenas que interfieren entre sí no pueden usar la misma frecuencia; el grado máximo acota cuántas frecuencias hacen falta.
  • Registros en compiladores. Variables que están vivas a la vez no pueden compartir registro del procesador.

Relación con otros resultados

Brooks es uno de los resultados básicos de la teoría de grafos, junto con el teorema de los cuatro colores para grafos planos (χ ≤ 4). Para grafos planos con Δ alto, el de los cuatro colores es mucho mejor; para grafos no planos de grado bajo, Brooks es el que da información. Si te interesa ver dónde encaja dentro de las matemáticas, tienes una lista comentada de los teoremas más importantes de las matemáticas. Y si vienes de la lógica y los circuitos, la coloración de grafos es también un problema de satisfacibilidad que se puede escribir en álgebra de Boole: una variable por cada par vértice-color y una cláusula por cada arista. Para el vocabulario de enunciado, hipótesis y demostración, la guía sobre qué es un teorema es un buen punto de partida.

Una nota sobre las búsquedas: «teorema de Chasles» no tiene relación con Brooks. Es un nombre que recibe un resultado de cinemática (todo desplazamiento de un sólido rígido es una rotación seguida de una traslación a lo largo del mismo eje).

Preguntas frecuentes

¿Qué dice el teorema de Brooks?

Que todo grafo conexo con grado máximo Δ se puede colorear con Δ colores, salvo si es un grafo completo o un ciclo impar, que necesitan Δ + 1.

¿Por qué los ciclos impares son una excepción?

Porque tienen grado máximo 2 y, al colorear alternando dos colores, el último vértice queda unido al primero con el mismo color. Necesitan 3 colores, uno más que Δ.

¿Quién demostró el teorema de Brooks y cuándo?

R. Leonard Brooks, en 1941, en Proceedings of the Cambridge Philosophical Society. László Lovász dio en 1975 una demostración más corta.

¿El teorema de Brooks da el número cromático exacto?

No, da una cota superior. Puede ser exacta (grafo de Petersen: Δ = 3 y χ = 3) o muy holgada (una estrella con Δ = 5 tiene χ = 2).

Fuentes

Teoremas

RELACIONADOS

Subir