Coloration des graphes — Nombre chromatique et applications

La coloration des graphes désigne le plus souvent la coloration des sommets : on attribue une couleur à chaque sommet de sorte que deux sommets adjacents n’aient pas la même couleur. Le plus petit nombre de couleurs qui convient est le nombre chromatique, noté $\chi(G)$.

Si vous voulez l’intuition rapide, les couleurs ne sont que des étiquettes sans conflit. Deux sommets peuvent réutiliser la même couleur exactement lorsqu’il n’y a pas d’arête entre eux.

Définition de la coloration des graphes en une minute

Dans une coloration propre, chaque arête relie deux sommets de couleurs différentes. C’est toute la règle.

Donc si $\chi(G)=3$, deux faits sont vrais en même temps :

• il existe une coloration propre avec $3$ couleurs
• il n’existe aucune coloration propre avec seulement $2$ couleurs

C’est pourquoi le nombre chromatique est un minimum, et pas simplement le nombre de couleurs que vous avez utilisé dans un dessin donné.

Sauf indication contraire, dans un cours d’introduction, la coloration des graphes signifie la coloration des sommets d’un graphe simple non orienté. La coloration des arêtes est un autre problème, avec d’autres règles.

Ce que mesure réellement le nombre chromatique

Le nom des couleurs n’a aucune importance. Vous pouvez utiliser rouge, bleu et vert, ou les étiquettes $1$, $2$ et $3$.

Ce qui compte, c’est le regroupement. Tous les sommets de même couleur forment un ensemble sans arêtes internes, donc ce groupe ne contient aucun conflit.

C’est ce point de vue qui rend la coloration des graphes utile dans les problèmes d’ordonnancement et d’allocation. Une couleur signifie souvent : « ces éléments peuvent partager le même créneau ».

Exemple détaillé : pourquoi un cycle à 5 sommets demande 3 couleurs

Considérons le graphe cycle $C_5$ avec les arêtes $AB, BC, CD, DE,$ et $EA$.

Essayez d’abord avec $2$ couleurs. Donnez à $A$ la couleur $1$ et à $B$ la couleur $2$. Alors la coloration est imposée tout autour du cycle :

$$A=1,\quad B=2,\quad C=1,\quad D=2$$

Regardons maintenant $E$. Il est adjacent à la fois à $D$ et à $A$, donc il ne peut pas utiliser la couleur $2$ à cause de $D$, et il ne peut pas utiliser la couleur $1$ à cause de $A$.

Donc $2$ couleurs ne suffisent pas.

Mais $3$ couleurs fonctionnent. Une coloration propre possible est

$$A=1,\quad B=2,\quad C=1,\quad D=2,\quad E=3$$

donc

$$\chi(C_5)=3$$

Cet exemple mérite d’être retenu, car il montre un schéma important : pour les graphes cycles, un cycle pair peut être colorié avec $2$ couleurs, mais un cycle impair demande $3$ couleurs.

Comment raisonner sur la coloration des graphes de petite taille

Deux vérifications rapides aident.

D’abord, cherchez un conflit inévitable. Dans l’exemple ci-dessus, alterner deux couleurs le long d’un cycle impair fait que le dernier sommet entre en conflit avec les deux choix disponibles.

Ensuite, cherchez une borne inférieure. Si un graphe contient un triangle, alors ces trois sommets sont adjacents deux à deux, donc ils demandent déjà $3$ couleurs différentes. Cela ne donne pas toujours la réponse exacte, mais cela prouve que le nombre chromatique est au moins $3$.

Erreurs fréquentes dans les problèmes de coloration des graphes

Une erreur fréquente consiste à considérer des sommets comme adjacents simplement parce qu’ils sont dessinés proches l’un de l’autre. Seule une arête réelle crée une contrainte de coloration.

Une autre erreur consiste à supposer que chaque sommet a besoin de sa propre couleur. Des sommets non adjacents peuvent réutiliser une couleur, et les colorations efficaces réutilisent généralement les couleurs autant que possible.

Les étudiants confondent aussi parfois la coloration des sommets et la coloration des arêtes. Dans cette page, la règle concerne les sommets adjacents, pas les arêtes adjacentes.

Une dernière erreur consiste à donner le nombre de couleurs que vous avez utilisé au lieu du nombre minimal nécessaire. Utiliser $4$ couleurs sur un graphe ne prouve pas que le nombre chromatique vaut $4$.

Où la coloration des graphes est utilisée

Une application classique est l’ordonnancement. Supposons que chaque sommet représente un examen, et qu’une arête signifie que deux examens ont des étudiants en commun et ne peuvent pas avoir lieu en même temps. Alors une couleur peut représenter un créneau horaire.

Dans ce modèle, le nombre chromatique vous donne le plus petit nombre possible de créneaux. Si $\chi(G)=4$, alors aucun emploi du temps valide avec seulement $3$ créneaux n’existe.

La même idée apparaît dans la coloration des cartes, où des régions voisines doivent être différentes, et dans la conception des compilateurs, où des variables nécessaires simultanément ne peuvent pas partager le même registre.

Essayez un problème de coloration des graphes similaire

Dessinez un graphe avec les sommets $P,Q,R,S,T$ et les arêtes $PQ, QR, RS, ST, TP,$ et $PR$.

Commencez par repérer un triangle pour obtenir une borne inférieure. Essayez ensuite de colorier le graphe avec aussi peu de couleurs que possible et vérifiez si des sommets adjacents ont la même couleur. Si vous voulez aller plus loin, essayez votre propre version sur un graphe plus grand et voyez si vous pouvez prouver que votre coloration est minimale, et pas seulement valide.