Teorema de Brooks

En matemáticas , especialmente en la teoría de grafos , el teorema de Brooks da una relación entre el grado máximo de un gráfico conectado no dirigido y el número cromático .

De acuerdo con este teorema, en un gráfico donde cada vértice tiene como máximo Δ vecinos , los vértices se pueden colorear con como máximo Δ colores, sin que dos vértices adyacentes tengan el mismo color, excepto en dos casos, los gráficos completos y los gráficos impares. ciclos de longitud, que necesitan Δ + 1 colores.

Estados

Teorema  :  en cualquier gráfico no dirigido G conectado de grado máximo Δ, el número cromático χ (G) satisface χ (G) ≤ Δ, a menos que G sea ​​un gráfico completo o un ciclo de longitud impar, en cuyo caso χ (G) = Δ + 1.

Historia y antecedentes

El teorema lleva el nombre de R. Leonard Brooks , quien publicó una prueba de él en 1941. La tinción con el número de colores descritos por el teorema de Brooks a veces se denomina tinción de Brooks o tinción Δ- . László Lovász dio una demostración más simple del teorema en 1975.

No es muy difícil demostrar que, para cualquier gráfico, χ (G) ≤ Δ + 1. De hecho, cualquier vértice v tiene como máximo Δ vértices vecinos, que en el peor de los casos son todos de colores diferentes. Incluso en este caso, siempre podemos tomar el (Δ + 1) ésimo color al color v . El mérito de Brooks ha sido reducir este aumento en 1 unidad en la mayoría de los casos.

Demostración

Hay varias pruebas del teorema de Brooks. Por ejemplo, podemos razonar por inducción sobre el número de vértices del gráfico. La siguiente demostración procede de manera diferente, se basa en el algoritmo codicioso para colorear gráficos y por lo tanto tiene el mérito de proporcionar algoritmos para colorear el gráfico (es una demostración constructiva ).

Esta demostración fue presentada por Ross Churchley en 2010 basada en el trabajo de John Adrian Bondy en 2003. El final reemplaza el razonamiento de Bondy con otros trabajos para no tener que apelar primero a los resultados relacionados con los árboles de rango profundo .

A continuación, examinamos sucesivamente cuatro casos:

• gráficos no regulares;
• gráficos regulares no biconectados;
• gráficos regulares biconectados de grado inferior a 3;
• Gráficos regulares biconectados de grado mayor o igual a 3.

Caso de gráficos no regulares

El principio, en el caso de grafos no regulares , es ordenar los vértices de cierta manera y luego colorearlos uno tras otro usando el algoritmo codicioso .

Sea G un gráfico no regular con n vértices y grado máximo Δ. Como G no es regular, existe al menos un vértice x de grado s estrictamente menor que Δ. Colocamos este vértice al final de la programación, es decir v n = x (figura 1) . Los vértices adyacentes ax se colocan justo antes en este orden, es decir en v n-s , v n-s-1 ,…, v n-1 (figura 2) .

Luego consideramos los vértices adyacentes a v n-1 que aún no han sido ordenados (figura 3) , luego los que están adyacentes a v n-2 y que aún no han sido ordenados, y así sucesivamente hasta ordenarlos todos, que es posible ya que G está conectado (figura 4) .

En este orden (v 1 , v 2 ,…, v n ) , todos los vértices tienen al menos un vértice adyacente posterior (de mayor índice), excepto el vértice x . En consecuencia, todos tienen, excepto el vértice x , un número de vértices adyacentes anteriores (de índice más bajo) estrictamente menor que Δ. El último vértice x también tiene, por su elección inicial, un número de vértices adyacentes anteriores estrictamente menores que Δ.

Luego coloreamos los vértices v i uno tras otro, para i variando de 1 a n . En cada paso, el vértice v i aún no se ha coloreado. Sus vértices adyacentes anteriores, que ya han sido coloreados, tienen un número máximo de Δ - 1, y por lo tanto utilizan a fortiori un máximo de Δ - 1 colores. Por tanto, podemos tomar para el nuevo vértice, en el peor de los casos, el color restante entre Δ (figuras 5 a 8) .

Caso de gráficos regulares no biconectados

En un gráfico no biconectado, hay al menos un punto de articulación , es decir, un vértice que, si se elimina, hace que el gráfico no esté conectado.

Considere un gráfico G regular de grado Δ no biconectado y sea x un punto de articulación de G (en rojo en la figura 1).

Descomponemos G multiplicando el punto de articulación como en la figura 2. Obtenemos al menos dos gráficos no regulares conectados de grado máximo Δ: de hecho, los vértices obtenidos al multiplicar x son cada uno de grados estrictamente menores que Δ.

Por tanto, se vuelve al caso anterior y se puede colorear cada componente conectado no regular utilizando el método expuesto anteriormente. Podemos disponer que los vértices obtenidos multiplicando x tengan el mismo color: para ello, intercambiamos los colores dentro de los componentes conectados si es necesario.

Todo lo que queda es volver a ensamblar las partes del gráfico para obtener un gráfico coloreado con colores Δ.

Caso de gráficos regulares biconectados de grado inferior a 3

El único gráfico regular conectado de grado 0 es el gráfico regular 0 compuesto por un solo vértice. Se puede colorear con 1 color (figura 1) . Como cae en la categoría de gráficos completos, satisface el enunciado del teorema de Brooks.

El único gráfico regular de 1 grado conectado es el gráfico regular 1 que consta de solo dos vértices, con un borde entre estos dos vértices (figura 2) . Se puede colorear con 2 colores y aquí también estamos en el caso de un gráfico completo: satisface el enunciado del teorema de Brooks.

Los únicos gráficos regulares conectados de grado 2 son los ciclos. Los ciclos con un número par de vértices se pueden colorear con 2 colores (figura 4) , y se necesitan 3 colores para ciclos con un número impar de vértices (figuras 3 y 5) . En ambos casos, se cumple el enunciado del teorema de Brooks.

Caso de gráficos regulares biconectados de grado mayor o igual a 3

Si el gráfico G es completo y de grado Δ, tiene Δ + 1 vértices que podemos cada color con un color diferente. También en este caso se cumple el enunciado del teorema de Brooks.

Si el gráfico no está completo, volveremos a ordenar un cierto número de vértices y luego los colorearemos usando el algoritmo codicioso. Sin embargo, no es tan sencillo como en el caso del gráfico no regular, porque nada garantiza a priori tener un color libre cuando llegamos al último vértice. Por lo tanto, vamos a organizar para el último color vértice v para tener dos vecinos u y w ya coloreado en el mismo color, lo que garantiza que vamos a tener al menos un color más libre a la hora de colorear v .

Sea G un no completa, gráfico biconexas de Δ grado ≥ 3. Hay tres vértices u , v y w tal que

• u está conectado av  ;
• v está conectado con w  ;
• pero u no está conectado con w .

Demostración Lema 1 En un gráfico G conectado e incompleto, podemos encontrar vértices u y w vecinos del mismo vértice v , pero no vecinos entre sí.

Como G no es completa, hay dos vértices de una y b que no están conectados directamente por un borde. A medida que la gráfica está conectada, existe una ruta ( a , v 1 , v 2 ,…, v p , b ) que conecta a con b . Sea i el valor más grande tal que v i esté relacionado con a . Considere u = a , v = v i y w = v i + 1 . Estos tres vértices verificar que u y w están vinculados a v sin estar vinculados entre sí.

Como se biconexo el gráfico, podemos eliminar u o w de ella sin dejar de ser conectado: G - { u } y G - { w } están conectados. Incluso podemos lograr tomar u , v y w de manera que G - { u , w } todavía esté conectado.

Demostración Lema 2 En un grafo G biconectado, de grado mínimo 3 o más y no completo, podemos encontrar vértices u y w vecinos al mismo vértice v , pero no vecinos entre ellos, de modo que G - { u , w } todavía está conectado.

Como el gráfico no está completo, existe al menos un vértice a que no es adyacente a todos los demás.

Si G - { a } se biconexo, tomamos, como en la prueba del lema 1, u = un y w igual a cualquier vértice en una distancia 2 de una . Dado que G - { a } está biconectado, podemos eliminar w sin perder conectividad, y G - { u , w } está conectado.

Considere ahora el caso en el que G - { a } está conectado, pero no biconectado. Por tanto, tiene puntos de articulación (en rojo en la figura) . Sea z uno de estos puntos de articulación. G - { a , z } no está conectado, incluso está dividido en al menos dos componentes conectados separados. Cada uno de estos componentes conectados V 1 , V 2 ,… V n se puede cortar a su vez en componentes biconectados conectados por los puntos de articulación. Estos componentes biconectados forman un árbol con raíz z .

En G, a tiene un vecino en cada una de las hojas al final de este árbol. De hecho, si eliminamos el punto de articulación z i al que está unida la hoja, si no estuviera conectado a a en el otro extremo, G - { z i } estaría desconectado, lo cual es imposible, ya que G está biconectado.

Tomemos u en una de las hojas al final de V 1 y w en una de las hojas al final de V 2 y sea v = a . Los vértices u y w están muy cerca de v . No son adyacentes, ya que se toman de diferentes componentes conectados.

Los vértices u y w están tomando en vértice de corte de G - { a } mientras que ser diferentes de los puntos de articulación de G - { a }, G - { a , u , w } permanece conectado. Como, además, el grado de a es mayor o igual a 3, existe un tercer vértice que permite conectar a con G - { a , u , w }. Por tanto, el gráfico G - { u , w } está conectado.

Como G - { u , w } está conectado, podemos ordenarlo como en los casos anteriores dando v el número más fuerte. Luego coloreamos G de la siguiente manera:

• coloreamos u y w con el mismo color, que es posible, ya que no están conectados (figura 1)  ;
• luego coloreamos el resto del gráfico respetando el orden que acabamos de establecer. Dado que cada uno de los vértices, excepto el último, tiene al menos un vecino sin color, tiene como máximo Δ - 1 vecinos de color y se puede colorear mientras permanece dentro de los colores Δ impuestos.

Cuando llegamos a colorear el último vértice v , tenemos la garantía de que sigue existiendo un color libre, puesto que sus dos vecinos u y w tienen el mismo color (figura 2) .

Resultados vecinos

Una generalización del teorema de Brooks se aplica a la coloración de listas  : dado un gráfico no dirigido y conectado de grado máximo Δ que no es ni un gráfico completo ni un ciclo de longitud impar, y una lista de colores Δ para cada vértice, es posible elegir un color para cada vértice tomado en su lista de modo que dos vértices adyacentes nunca tengan el mismo color. En otras palabras, el número cromático de la lista de un gráfico conectado no dirigido nunca es mayor que Δ, excepto en el caso de un gráfico completo o un ciclo de longitud impar. Esto fue demostrado por Vadim Vizing en 1976.

Con algunos gráficos, incluso necesitamos menos colores Δ. Bruce Reed muestra que los colores Δ - 1 son suficientes si y solo si el gráfico no tiene Δ- clics cuando Δ es lo suficientemente grande. Para gráficos sin triángulo (sin un conjunto de tres vértices adyacentes en pares), o más generalmente para gráficos donde la vecindad de cada vértice es suficientemente hueca , los colores O (Δ / log Δ) son suficientes.

El grado de un gráfico también aparece en los límites superiores del número de colores necesarios para otros tipos de coloración:

• en la coloración de los bordes de un gráfico , el resultado según el cual el índice cromático es menor o igual que Δ + 1 es el teorema de Vizing ;
• Behzad y Vizing han conjeturado una extensión del teorema de Brooks a la coloración total  (en) de un gráfico que afirma que el número cromático total es como máximo Δ + 2;
• el teorema de Hajnal- Szemerédi sobre la coloración equitativa de un gráfico establece que cualquier gráfico se puede colorear con un máximo de colores Δ + 1 de modo que el número de vértices de cada color difiera como máximo en 1.

Algoritmos

Se puede obtener una coloración con Δ colores, o incluso una coloración por lista con Δ colores, de un gráfico de grado máximo Δ en un tiempo lineal (proporcional al número de vértices y aristas). También se conocen algoritmos eficientes que permiten encontrar tinciones de Brooks mediante procesamiento paralelo o distribuido.

Notas y referencias

1. (en) RL Brooks , "  está coloreando los nodos de una red  " , Proc. Sociedad Filosófica de Cambridge, Matemáticas. Phys. Sci. , vol.  37,1941, p.  194-197 ( leer en línea ).
2. (in) L. Lovász , "  Tres breves demostraciones en teoría de grafos  " , J. Combin. Th., Serie B , vol.  19,1975, p.  269–271 ( DOI  10.1016 / 0095-8956 (75) 90089-1 )
3. (en) Ross Churchley, "  Haiku de la teoría de grafos: tres cortos y hermosas pruebas  ", noviembre de 2010.
4. (en) JA Bondy , "  Pruebas breves de teoremas clásicos  " , Journal of Graph Theory , vol.  44, n o  3,noviembre de 2003, p.  159 hasta 165
5. (en) Bradley Baetz y David R. Wood, "  Teorema de coloración de vértices de Brooks en tiempo lineal , Informe técnico CS-AAG-2001-05, Universidad de Sydney, octubre de 2001.
6. (en) Dieter Jungnickel, "  Gráficos, redes y algoritmos  ", volumen 5, segunda edición, Springer Verlag, mayo de 2003 ( ISBN  3-540-63760-5 ) .
7. (ru) VG Vizing , "  Coloreaciones de vértices con colores dados  " , Diskret. Analiz. , vol.  29,1976, p.  3–10
8. (en) Bruce Reed , "  Fortalecimiento del teorema de Brooks  " , J. Combin. Th., Serie B , vol.  76, n o  21999, p.  136–149 ( DOI  10.1006 / jctb.1998.1891 )
9. (en) Noga Alon Michael Krivelevich y Benny Sudakov , "  Colorear gráficos con barrios dispersos  " , J. Combin. Th., Serie B , vol.  77, n o  1,1999, p.  73–82 ( DOI  10.1006 / jctb.1999.1910 )
10. (in) San Skulrattanakulchai , "  Coloración de vértices de lista Δ en tiempo lineal  " , Inf. Proceso. Letón. , vol.  98, n o  3,2006, p.  101–106 ( DOI  10.1016 / j.ipl.2005.12.007 )
11. (en) HJ Karloff , "  Un algoritmo para el teorema de NC Brooks  " , TCS , vol.  68, n o  1,1989, p.  89–103 ( DOI  10.1016 / 0304-3975 (89) 90121-7 )
12. (in) Péter Hajnal y Endre Szemerédi , "  Brooks coloreando en paralelo  " , SIAM J. Discrete Math. , vol.  3, n o  1,1990, p.  74–80 ( DOI  10.1137 / 0403008 )
13. (in) Alessandro Panconesi y Aravind Srinivasan , "  El tipo local de coloración Δ y sus aplicaciones algorítmicas  " , combinatorica , vol.  15, n o  21995, p.  255–280 ( DOI  10.1007 / BF01200759 )
14. (en) David A. Grable y Alessandro Panconesi , "algoritmos rápidos para colorantes Brooks-Vizing distribuidos" en SODA 98: Actas de la novena anual ACM-SIAM Simposio sobre algoritmos discretos , Filadelfia, PA, EE.UU., SIAM , al.  "Diario de Algoritmos" ( n o  37),1998( DOI  10.1006 / jagm.2000.1097 , leer en línea )

Enlace externo

(en) Eric W. Weisstein , "  Teorema de Brooks  " , en MathWorld