Loading AI tools
De Wikipédia, l'encyclopédie libre
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.
Théorème — Dans tout graphe connexe non orienté G de degré maximal Δ, le nombre chromatique χ(G) vérifie χ(G) ≤ Δ, sauf si G est un graphe complet ou un cycle de longueur impaire, auquel cas χ(G) = Δ + 1.
Le théorème porte le nom de R. Leonard Brooks, qui en a publié une démonstration en 1941[1]. 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[2].
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[3] d'après les travaux de John Adrian Bondy en 2003[4]. 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 :
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 vn = x (figure 1). Les sommets adjacents à x sont placés juste avant dans cet ordonnancement, c'est-à-dire en vn-s, vn-s-1, …, vn-1 (figure 2).
On considère ensuite les sommets adjacents à vn-1 qui n'ont pas déjà été ordonnés (figure 3), puis ceux qui sont adjacents à vn-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 (v1, v2, …, vn), 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 vi les uns après les autres, pour i variant de 1 à n. À chaque étape, le sommet vi 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
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 :
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).
Une généralisation du théorème de Brooks s'applique à la coloration par liste : étant donné un graphe non orienté et connexe de degré maximal Δ qui n'est ni un graphe complet ni un cycle de longueur impaire, et une liste de Δ couleurs pour chaque sommet, il est possible de choisir une couleur pour chaque sommet prise dans sa liste de manière que deux sommets adjacents n'aient jamais la même couleur. En d'autres termes, le nombre chromatique de liste d'un graphe connexe non orienté n'est jamais plus grand que Δ, sauf dans le cas d'un graphe complet ou d'un cycle de longueur impaire. Cela a été démontré par Vadim Vizing en 1976[7].
Avec certains graphes, on a même besoin de moins de Δ couleurs. Bruce Reed montre que Δ − 1 couleurs suffisent si et seulement si le graphe n'a pas de Δ-clique lorsque Δ est suffisamment grand[8]. Pour les graphes sans triangle (sans ensemble de trois sommets adjacents deux à deux), ou plus généralement les graphes où le voisinage de chaque sommet est suffisamment creux, O(Δ / log Δ) couleurs suffisent[9].
Le degré d'un graphe apparaît aussi dans les bornes supérieures du nombre de couleurs nécessaires à d'autres types de colorations :
Une coloration avec Δ couleurs, ou même une coloration par liste avec Δ couleurs, d'un graphe de degré maximal Δ peut être obtenue dans un temps linéaire (proportionnel au nombre de sommets et d'arêtes)[10]. Des algorithmes efficaces qui permettent de trouver des colorations de Brooks en utilisant des traitements parallèles ou distribués sont également connus[11],[12],[13],[14].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.