En teoría de grafos , el teorema de Brooks establece una relación entre el grado máximo de una gráfica y su número cromático . Según el teorema, en un gráfico conectado en el que cada vértice tiene como máximo Δ vecinos, los vértices se pueden colorear solo con Δ colores, excepto en dos casos, gráficos completos y gráficos cíclicos de longitud impar, que requieren Δ + 1 colores.
El teorema lleva el nombre de R. Leonard Brooks , quien publicó una prueba del mismo en 1941. Una coloración con el número de colores descritos por el teorema de Brooks a veces se denomina coloración de Brooks o coloración Δ .
Para cualquier gráfico no dirigido conectado G con grado máximo Δ, el número cromático de G es como máximo Δ, a menos que G sea un gráfico completo o un ciclo impar, en cuyo caso el número cromático es Δ + 1.
László Lovász (1975) ofrece una prueba simplificada del teorema de Brooks. Si el gráfico no es biconexo , sus componentes biconexos se pueden colorear por separado y luego combinar los colores. Si el gráfico tiene un vértice v con un grado menor que Δ, entonces un algoritmo de coloración codicioso 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 cada vértice distinto de v está coloreado, al menos uno de sus vecinos (el que está en el 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 alcanza v , su pequeño número de vecinos permite colorearlo. Por lo tanto, el caso más difícil de la prueba se refiere a gráficos Δ- regulares biconectados con Δ ≥ 3. En este caso, Lovász muestra que se puede encontrar un árbol generador tal que dos vecinos no adyacentes u y w de la raíz v sean hojas en el árbol. . Una coloración codiciosa que comienza en u y w y procesa los vértices restantes del árbol de expansión en orden de abajo hacia arriba, 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 en sí mismo.
Se aplica una versión más general del teorema a la coloración de listas : dado cualquier gráfico no dirigido conectado 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 para que no haya dos vértices adyacentes que tengan el mismo color. En otras palabras, el número cromático de lista de un gráfico no dirigido conectado G nunca excede Δ, a menos que G sea una camarilla o un ciclo impar. Esto lo ha demostrado Vadim Vizing (1976). 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, dé a u y w el mismo color entre sí (si es posible), o de lo contrario, dé uno de ellos. un color que no está disponible para v y luego completa la coloración con avidez como antes.
Para ciertos gráficos, es posible que se necesiten incluso menos colores que Δ. Bruce Reed (1999) muestra que Δ − 1 colores son suficientes si y sólo si el gráfico dado no tiene Δ-clique, siempre que Δ sea lo suficientemente grande. Para gráficos sin triángulos , o más generalmente gráficos en los que la vecindad de cada vértice es suficientemente escasa , los colores O(Δ/log Δ) son suficientes. [1]
El grado de un gráfico también aparece en los límites superiores para otros tipos de coloración; para la coloración de 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 , afirmando 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 gráfico tiene una coloración (Δ + 1) en la que los tamaños de dos clases de colores cualesquiera difieren como máximo en uno.
Se puede encontrar una coloración Δ, o incluso una coloración de lista Δ, de un gráfico de grados Δ en el tiempo lineal. [2] También se conocen algoritmos eficientes para encontrar coloraciones de Brooks en modelos de computación paralelos y distribuidos. [3]