Teorema de Brooks

En teoria de grafos, la teorema de Brooks establix la relació entre la valència màxima del grafo en el número cromàtic:

Si G és un grafo conexo que no siga complet ni un cicle de llongitut impar, llavors $\chi (G)\le \Delta$ R. L. Brooks, (1941)

En a on $\Delta$ és la valència màxima del grafo G.

Demostració bàsica

La següent demostració és només per a grafos no regulars. Basta buscar una ordenació adequada i aplicar l'algoritme voraç para colorear secuencialmente.

Siga G un grafo de n vèrtiços i x un vèrtiç tal que $g(x)=s<\Delta$ (que existix per la no regularitat). El vèrtiç x ho coloquem en l'últim lloc de l'ordenació, és dir, x=v_n . Els vèrtiços adjacents a x els enumerem v_n-s, v_n-s-1, ..., v_n-1, després considerem els adjacents a v_n-1 que no han segut ordenats, després els de v_n-2, i aixina fins a ordenar-los tots (la qual cosa és possible en ser G conexo).

En esta ordenació {v₁, v₂, ..., v_n}, tots els vèrtiços tenen un vèrtiç (o més) adjacent posterior (en subíndex major) llevat el vèrtiç x . Després, el número de vèrtiços adjacents en subíndex menor és igual o menor a Δ .

En aplicar l'algoritme voraç per a colorear sorgixen els colors prohibits. El número de colors prohibits en el pas k de l'eixecució de l'algoritme és el número de colors usats per lo vèrtiços adjacents anteriors, i pels vèrtiços anteriors. Després, en cada pas de l'algoritme hi ha com a molt Δ-1 colors prohibits. Per lo tant, es pot colorear G en Δ colors.

Referències

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