Teorema de Brooks

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En teoría de grafos, el teorema de Brooks establece la relación entre la valencia máxima del grafo con el número cromático:

Si G es un grafo conexo que no sea completo ni un ciclo de longitud impar, entonces \chi (G)\le \Delta \,


R. L. Brooks, (1941)

En donde \Delta es la valencia máxima del grafo G.

Demostración básica[editar]

La siguiente demostración es sólo para grafos no regulares. Basta buscar una ordenación adecuada y aplicar el algoritmo voraz para colorear secuencialmente.

Sea G un grafo de n vértices y x un vértice tal que g(x)=s < \Delta \,  (que existe por la no regularidad). El vértice x lo colocamos en el último lugar de la ordenación, es decir, x=vn . Los vértices adyacentes a x los enumeramos vn-s, vn-s-1, ..., vn-1, luego consideramos los adyacentes a vn-1 que no han sido ordenados, luego los de vn-2, y así hasta ordenarlos todos (lo cual es posible al ser G conexo).

En esta ordenación {v1, v2, ..., vn}, todos los vértices tienen un vértice (o más) adyacente posterior (con subíndice mayor) excepto el vértice x . Luego, el número de vértices adyacentes con subíndice menor es igual o menor a Δ .

Al aplicar el algoritmo voraz para colorear surgen los colores prohibidos. El número de colores prohibidos en el paso k de la ejecución del algoritmo es el número de colores usados por lo vértices adyacentes anteriores, y por los vértices anteriores. Luego, en cada paso del algoritmo hay a lo sumo Δ-1 colores prohibidos. Por lo tanto, se puede colorear G con Δ colores.

Referencias[editar]

  • Brooks, R. L. (1941), "On colouring the nodes of a network", Proc. Cambridge Philosophical Society, Math. Phys. Sci. 37: 194–197