Déterminer le nombre chromatique d’un graphe
Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.
Créer un compteRemarque
Bonus hors programme (culture) : la coloration et le nombre chromatique ne figurent pas au programme de l'option Mathématiques expertes. Cette méthode est proposée à titre de complément.
Méthode
Pour déterminer le nombre chromatique $\chi$ d'un graphe :
Étape 1 : calculer le degré maximal $d_{\max}$ du graphe. On en déduit la borne supérieure :
$\chi \leqslant d_{\max} + 1$Étape 2 : chercher dans le graphe un sous-graphe complet (clique) : un ensemble de sommets tous deux à deux adjacents. Si le sous-graphe complet contient $p$ sommets, on en déduit la borne inférieure :
$\chi \geqslant p$- Étape 3 : proposer un coloriage explicite du graphe en utilisant le minimum de couleurs possible. On colorie de proche en proche, en attribuant à chaque sommet la première couleur disponible.
- Étape 4 : conclure : si le coloriage utilise exactement $p$ couleurs et que la borne inférieure vaut $p$, alors $\chi = p$.
Pentagone : un cycle impair
On considère le graphe ci-dessous (cycle à $5$ sommets $A, B, C, D, E$).
Étape 1 : Tous les sommets sont de degré $2$, donc $d_{\max} = 2$. On en déduit :
Étape 2 : Le graphe ne contient aucun triangle (sous-graphe complet d'ordre $3$). Le plus grand sous-graphe complet est une simple arête (deux sommets adjacents), d'où la borne inférieure $\chi \geqslant 2$.
À ce stade : $2 \leqslant \chi \leqslant 3$.
Étape 3 : On essaie de colorier avec $2$ couleurs (rouge et bleu) :
- $A$ rouge, $B$ bleu, $C$ rouge, $D$ bleu, $E$ doit être différent de $D$ (bleu) et de $A$ (rouge).
- Aucune des deux couleurs ne convient pour $E$.
Avec $3$ couleurs (rouge, bleu, vert) : $A$ rouge, $B$ bleu, $C$ rouge, $D$ bleu, $E$ vert. Tous les sommets adjacents ont des couleurs différentes.
Étape 4 : Le coloriage utilise $3$ couleurs et $2$ ne suffisent pas, donc $\chi = 3$.
Graphe contenant un sous-graphe complet d'ordre 4
On considère le graphe ci-dessous, où $A, B, C, D$ forment un sous-graphe complet $K_4$ (chacun est relié aux trois autres) et $E$ est relié à $A$ uniquement.
Étape 1 : Le sommet $A$ est relié à $B$, $C$, $D$, $E$, donc $\deg(A) = 4 = d_{\max}$. Ainsi :
Étape 2 : Les sommets $A$, $B$, $C$, $D$ forment un sous-graphe complet $K_4$ (toutes les arêtes sont présentes). On en déduit :
À ce stade : $4 \leqslant \chi \leqslant 5$.
Étape 3 : On essaie de colorier avec $4$ couleurs (rouge, bleu, vert, jaune) :
- $A$, $B$, $C$, $D$ forment $K_4$ et nécessitent donc $4$ couleurs distinctes : par exemple $A$ rouge, $B$ bleu, $C$ vert, $D$ jaune.
- $E$ n'est relié qu'à $A$ (rouge) ; on peut le colorier en bleu, vert ou jaune. On choisit bleu.
Le coloriage utilise $4$ couleurs et respecte la contrainte.
Étape 4 : La borne inférieure et le coloriage donnent tous deux $4$, donc $\chi = 4$.
Remarque
La borne supérieure $d_{\max} + 1$ est souvent grossière : pour le pentagone, elle donne $3$, ce qui correspond bien à $\chi$, mais pour le graphe complet $K_n$, on a $d_{\max} = n - 1$ et $\chi = n$, donc la borne est atteinte à l'ordre près.
L'approche gloutonne (algorithme de Welsh-Powell) consiste à classer les sommets par degré décroissant puis à attribuer à chacun la première couleur compatible avec ses voisins déjà coloriés.
Attention
Trouver un coloriage avec $k$ couleurs prouve $\chi \leqslant k$. Pour prouver $\chi = k$, il faut aussi établir une borne inférieure (par exemple en exhibant un sous-graphe complet d'ordre $k$, ou en montrant qu'un coloriage à $k - 1$ couleurs est impossible).
Trouver un coloriage à $4$ couleurs ne prouve donc pas que $\chi = 4$ : il pourrait exister un coloriage à $3$ couleurs.