Théorème de Brooks
En mathématiques, et plus particulièrement dans la théorie des graphes, le théorème de Brooks donne une relation entre le degré maximal d'un graphe connexe non orienté et son nombre chromatique. Selon ce théorème, dans un graphe où chaque sommet a au plus Δ voisins, les sommets peuvent être colorés avec au plus Δ couleurs, sans que deux sommets adjacents n'aient la même couleur, sauf dans deux cas, les graphes complets et les graphes cycles de longueur impaire, qui ont besoin de Δ + 1 couleurs. Le théorème porte le nom de R. Leonard Brooks, qui en a publié une démonstration en 1941. Une coloration avec le nombre de couleurs décrit par le théorème de Brooks est parfois appelée coloration de Brooks ou Δ-coloration. László Lovász a donné une démonstration plus simple du théorème en 1975. Il n'est pas très dur de démontrer que, pour tout graphe, χ(G) ≤ Δ + 1. En effet, n'importe quel sommet v possède au maximum Δ sommets voisins, qui dans le pire des cas sont tous de couleur différente. Même dans ce cas, on peut toujours prendre la (Δ + 1)ème couleur pour colorer v. Le mérite de Brooks a été de diminuer cette majoration de 1 unité dans la plupart des cas. Il existe plusieurs démonstrations du théorème de Brooks. On peut par exemple raisonner par récurrence sur le nombre de sommets du graphe. La démonstration qui suit procède autrement, elle s'appuie sur l'algorithme glouton de coloration des graphes et a donc le mérite de donner des algorithmes pour colorer le graphe (c'est une démonstration constructive). Cette démonstration a été présentée par Ross Churchley en 2010 d'après les travaux de John Adrian Bondy en 2003. La fin remplace le raisonnement de Bondy par d'autres travaux pour ne pas avoir à faire appel aux résultats concernant les arbres de parcours en profondeur d'abord. Dans ce qui suit, nous examinons successivement quatre cas : les graphes non réguliers ; les graphes réguliers non biconnexes ; les graphes réguliers biconnexes de degré inférieur à 3 ; les graphes réguliers biconnexes de degré supérieur ou égal à 3.
