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


R. L. Brooks, (1941)

En donde 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 (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