Théorème de Brooks

Le principe, dans le cas des graphes non réguliers, est d'ordonner les sommets d'une certaine façon, et ensuite de les colorer l'un après l'autre à l'aide de l'algorithme glouton.

Soit G un graphe non régulier à n sommets et de degré maximal Δ. Comme G n'est pas régulier, il existe au moins un sommet x de degré s strictement inférieur à Δ. On place ce sommet à la fin de l'ordonnancement, c'est-à-dire v_n = x (figure 1). Les sommets adjacents à x sont placés juste avant dans cet ordonnancement, c'est-à-dire en v_n-s, v_n-s-1, …, v_n-1 (figure 2).

On considère ensuite les sommets adjacents à v_n-1 qui n'ont pas déjà été ordonnés (figure 3), puis ceux qui sont adjacents à v_n-2 et qui n'ont pas encore été ordonnés, et ainsi de suite jusqu'à les ordonner tous, ce qui est possible puisque G est connexe (figure 4).

Dans cet ordonnancement (v₁, v₂, …, v_n), tous les sommets ont au moins un sommet adjacent postérieur (d'indice supérieur), sauf le sommet x. Par conséquent, ils ont tous, sauf le sommet x, un nombre de sommets adjacents antérieurs (d'indice inférieur) strictement inférieur à Δ. Le dernier sommet x a aussi, de par son choix initial, un nombre de sommets adjacents antérieurs strictement inférieur à Δ.

On colore ensuite les sommets v_i les uns après les autres, pour i variant de 1 à n. À chaque étape, le sommet v_i n'a pas encore été coloré. Ses sommets adjacents antérieurs, qui ont déjà été colorés, sont au maximum au nombre de Δ − 1, et utilisent donc a fortiori au maximum Δ − 1 couleurs. On peut donc prendre pour le nouveau sommet, dans le pire des cas, la couleur restante parmi Δ (figures 5 à 8).

Dans un graphe non biconnexe, il existe au moins un point d'articulation, c'est-à-dire un sommet qui, s'il est retiré, rend le graphe non connexe.

Considérons un tel graphe G régulier de degré Δ non biconnexe et soit x un point d'articulation de G (en rouge sur la figure 1).

On décompose G en démultipliant le point d'articulation comme sur la figure 2. On obtient au moins deux graphes non réguliers connexes de degré maximal Δ : en effet, les sommets obtenus en démultipliant x sont chacun de degré strictement inférieur à Δ.

On est donc ramené au cas précédent et on peut colorer chaque composante connexe non régulière en utilisant la méthode exposée auparavant. On peut s'arranger pour que les sommets obtenus en démultipliant x aient la même couleur : pour cela, on permute les couleurs au sein des composantes connexes si c'est nécessaire.

Il ne reste plus qu'à réassembler les parties de graphe pour obtenir un graphe coloré avec Δ couleurs.

Le seul graphe régulier de degré 0 qui soit connexe est le graphe 0-régulier composé d'un seul sommet. Il peut être coloré avec 1 couleur (figure 1). Comme il entre dans la catégorie des graphes complets, il vérifie l'énoncé du théorème de Brooks.

Le seul graphe régulier de degré 1 qui soit connexe est le graphe 1-régulier constitué de deux sommets seulement, avec une arête entre ces deux sommets (figure 2). Il peut être coloré avec 2 couleurs et là aussi on est dans le cas d'un graphe complet : il vérifie l'énoncé du théorème de Brooks.

Les seuls graphes réguliers connexes de degré 2 sont les cycles. Les cycles comportant un nombre de sommets pair peuvent être colorés avec 2 couleurs (figure 4), et il faut 3 couleurs pour les cycles comportant un nombre de sommets impair (figures 3 et 5). Dans les deux cas, l'énoncé du théorème de Brooks est vérifié.

Si le graphe G est complet et de degré Δ, il comporte Δ + 1 sommets que l'on peut chacun colorer avec une couleur différente. Dans ce cas aussi, l'énoncé du théorème de Brooks est vérifié.

Si le graphe n'est pas complet, on va de nouveau ordonner un certain nombre de sommets, puis les colorer à l'aide de l'algorithme glouton. Ce n'est toutefois pas aussi simple que dans le cas du graphe non régulier, car rien ne nous garantit a priori de disposer d'une couleur de libre quand on arrive au dernier sommet. On va donc s'arranger pour que le dernier sommet v coloré ait deux voisins u et w déjà colorés dans la même couleur, ce qui assure qu'on aura au moins encore une couleur de libre lorsqu'il s'agira de colorer v.

Soit G un graphe non complet, biconnexe, et de degré Δ ≥ 3. Il existe trois sommets u, v et w tels que

• u est relié à v ;
• v est relié à w ;
• mais u n'est pas relié à w.

Comme le graphe est biconnexe, on peut en retirer u ou w sans qu'il cesse d'être connexe : G - { u } et G - { w } sont connexes. On peut même s'arranger pour prendre u, v et w tels que G - { u, w } soit encore connexe.

Comme G - { u, w } est connexe, on peut l'ordonner comme dans les cas précédents en donnant à v le numéro le plus fort. On colore ensuite G de la manière suivante :

• on colore u et w avec la même couleur, ce qui est possible puisqu'ils ne sont pas reliés (figure 1) ;
• on colore ensuite le reste du graphe en respectant l'ordre que l'on vient d'établir. Comme chacun des sommets sauf le dernier possède au moins un voisin non coloré, il possède au plus Δ − 1 voisins colorés et peut être coloré en restant dans les Δ couleurs imposées.

Lorsqu'on en arrive à colorer le dernier sommet v, on a la garantie qu'il reste une couleur de libre, puisque ses deux voisins u et w ont la même couleur (figure 2).