En teoría de grafos , el teorema de Brooks establece una relación entre el grado máximo de un gráfico y su número cromático . De acuerdo con el teorema, en un gráfico conectado en el que cada vértice tiene como máximo Δ vecinos, los vértices se pueden colorear con solo Δ 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 llama coloración de Brooks o coloración Δ .
Declaración formal
Para cualquier gráfico G conectado no dirigido 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.
Prueba
László Lovász ( 1975 ) ofrece una demostración simplificada del teorema de Brooks. Si el gráfico no está biconectado , sus componentes biconectados 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 utiliza como máximo colores Δ. Por lo tanto, el caso más difícil de la demostración se refiere a gráficos regulares Δ biconectados 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 son hojas en el árbol. . Una coloración codiciosos partir de U y W y el procesamiento de los vértices restantes del árbol de expansión con el fin de abajo hacia arriba, terminando en v , usos en la mayoría de los colores delta. Porque, cuando todos los vértices que no sea v es de color, tiene un padre sin color, por lo que sus vecinos de colores ya-no pueden utilizar todos los colores libres, mientras que en contra de los dos vecinos u y w tienen colores iguales para volver a restos de color libres para v sí mismo.
Extensiones
Una versión más general del teorema se aplica a la coloración de listas : dado cualquier gráfico no dirigido conectado con grado máximo Δ que no sea ni una pandilla 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 del mismo color. En otras palabras, el número cromático de la lista de un gráfico conectado no dirigido G nunca excede Δ, a menos que G sea una pandilla o un ciclo impar. Esto ha sido probado por Vadim Vizing ( 1976 ). En este caso se aplica una pequeña modificación de la prueba de Lovász: para los mismos tres vértices u , v , yw de esa prueba, dale a u y w el mismo color que el otro (si es posible), o da uno de ellos. un color que no está disponible para v , y luego complete la coloración con avidez como antes.
Para ciertos gráficos, es posible que se necesiten incluso menos de Δ colores. Bruce Reed ( 1999 ) muestra que Δ - 1 colores son suficientes si y solo 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 lo 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 , 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 gráfico tiene una coloración (Δ + 1) en la que los tamaños de dos clases de colores difieren como máximo en uno.
Algoritmos
Se puede encontrar una coloración even, o incluso una coloración de lista a, de un gráfico de grados Δ en tiempo lineal. [2] También se conocen algoritmos eficientes para encontrar coloraciones de Brooks en modelos de cálculo paralelos y distribuidos. [3]
Notas
Referencias
- Alon, Noga ; Krivelevich, Michael ; Sudakov, Benny (1999), "Colorear gráficos con barrios dispersos", Journal of Combinatorial Theory , Serie B, 77 (1): 73–82, doi : 10.1006 / jctb.1999.1910
- Brooks, RL (1941), "Sobre colorear los nodos de una red", Procedimientos matemáticos de la Sociedad Filosófica de Cambridge , 37 (2): 194-197, doi : 10.1017 / S030500410002168X.
- Grable, David A .; Panconesi, Alessandro (2000), "Algoritmos distribuidos rápidamente para colorantes Brooks-Vizing", Journal of Algorithms , 37 : 85–120, doi : 10.1006 / jagm.2000.1097.
- Hajnal, Péter; Szemerédi, Endre (1990), "Brooks coloreando en paralelo", SIAM Journal on Discrete Mathematics , 3 (1): 74–80, doi : 10.1137 / 0403008.
- Karloff, HJ (1989), "Un algoritmo NC para el teorema de Brooks", Informática teórica , 68 (1): 89-103, doi : 10.1016 / 0304-3975 (89) 90121-7.
- Lovász, L. (1975), "Tres pruebas breves en la teoría de grafos", Journal of Combinatorial Theory , Serie B, 19 (3): 269-271, doi : 10.1016 / 0095-8956 (75) 90089-1.
- Panconesi, Alessandro; Srinivasan, Aravind (1995), "La naturaleza local de la coloración Δ y sus aplicaciones algorítmicas", Combinatorica , 15 (2): 255-280, doi : 10.1007 / BF01200759.
- Reed, Bruce (1999), "Un fortalecimiento del teorema de Brooks", Journal of Combinatorial Theory , Serie B, 76 (2): 136-149, doi : 10.1006 / jctb.1998.1891.
- Skulrattanakulchai, San (2006), "Coloración de vértices de lista Δ en tiempo lineal", Information Processing Letters , 98 (3): 101-106, doi : 10.1016 / j.ipl.2005.12.007.
- Vizing, VG (1976), " Coloreaciones de vértices con colores dados", Diskret. Analiz. (en ruso), 29 : 3–10.
enlaces externos
- Weisstein, Eric W. , "Teorema de Brooks" , MathWorld