En teoría de grafos , el teorema de Brooks establece una relación entre el grado máximo de un grafo y su número cromático . Según el teorema, en un grafo conexo en el que cada vértice tiene como máximo Δ vecinos, los vértices pueden colorearse con solo Δ colores, excepto en dos casos, grafos completos y grafos cíclicos de longitud impar, que requieren Δ + 1 colores.
El teorema recibe su nombre de R. Leonard Brooks , quien publicó una prueba del mismo en 1941. [1] Una coloración con la cantidad de colores descrita por el teorema de Brooks a veces se denomina coloración de Brooks [2] o coloración Δ . [3]
Para cualquier grafo conexo no dirigido G con grado máximo Δ, el número cromático de G es como máximo Δ, a menos que G sea un grafo completo o un ciclo impar, en cuyo caso el número cromático es Δ + 1. [1]
László Lovász ofrece una prueba simplificada del teorema de Brooks. Si el grafo no es biconexo , sus componentes biconexos pueden colorearse por separado y luego combinarse las coloraciones. Si el grafo tiene un vértice v con grado menor que Δ, entonces un algoritmo de coloración voraz que colorea los vértices más alejados de v antes que los más cercanos usa como máximo Δ colores. Esto se debe a que en el momento en que se colorea cada vértice distinto de v , al menos uno de sus vecinos (el que está en un camino más corto hacia v ) no está coloreado, por lo que tiene menos de Δ vecinos coloreados y tiene un color libre. Cuando el algoritmo llega a v , su pequeño número de vecinos le permite colorearlo. Por lo tanto, el caso más difícil de la prueba se refiere a los grafos Δ- regulares biconexos con Δ ≥ 3. En este caso, Lovász muestra que se puede encontrar un árbol de expansión tal que dos vecinos no adyacentes u y w de la raíz v sean hojas en el árbol. Una coloración voraz que comienza desde u y w y procesa los vértices restantes del árbol de expansión en orden ascendente, terminando en v , utiliza como máximo Δ colores. Porque, cuando cada vértice distinto de v está coloreado, tiene un padre sin color, por lo que sus vecinos ya coloreados no pueden usar todos los colores libres, mientras que en v los dos vecinos u y w tienen colores iguales, por lo que nuevamente queda un color libre para v . [4]
Una versión más general del teorema se aplica a la coloración de listas : dado cualquier grafo no dirigido conexo con grado máximo Δ que no sea ni una camarilla ni un ciclo impar, y una lista de Δ colores para cada vértice, es posible elegir un color para cada vértice de su lista de modo que no haya dos vértices adyacentes con el mismo color. En otras palabras, el número cromático de la lista de un grafo no dirigido conexo G nunca excede Δ, a menos que G sea una camarilla o un ciclo impar. [5] Una pequeña modificación de la prueba de Lovász se aplica a este caso: para los mismos tres vértices u , v y w de esa prueba, o bien se les da a u y w el mismo color entre sí (si es posible), o bien se les da a uno de ellos un color que no esté disponible para v , y luego se completa la coloración con avidez como antes.
Para ciertos gráficos, pueden necesitarse incluso menos de Δ colores. Δ − 1 colores son suficientes si y solo si el gráfico dado no tiene Δ-clique, siempre que Δ sea lo suficientemente grande. [6] Para gráficos sin triángulos , o más generalmente gráficos en los que la vecindad de cada vértice es suficientemente dispersa , O(Δ/log Δ) colores son suficientes. [7]
El grado de un grafo también aparece en los límites superiores para otros tipos de coloración; para la coloración de los bordes , el resultado de que el índice cromático es como máximo Δ + 1 es el teorema de Vizing . Mehdi Behzad y Vizing han conjeturado una extensión del teorema de Brooks a la coloración total , que establece que el número cromático total es como máximo Δ + 2. El teorema de Hajnal-Szemerédi sobre coloración equitativa establece que cualquier grafo tiene una coloración (Δ + 1) en la que los tamaños de dos clases de color cualesquiera difieren como máximo en uno.
Se puede encontrar una coloración Δ, o incluso una coloración Δ-lista, de un gráfico de grado Δ en tiempo lineal. [8] También se conocen algoritmos eficientes para encontrar coloraciones de Brooks en modelos de computación paralelos y distribuidos. [9]