théorème de Brooks

COMBINATOIRE

Le théorème de Brooks est un théorème de coloration dans le cadre de la théorie des graphes. Il 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 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 est appelé théorème du nom du matématicien britannique R. Leonard Brooks qui l’a démontré en 1941.