ArithmétiqueObjet mathématique · Glossaire
nombre chromatique d'un graphe
La coloration d'un graphe est une notion fondamentale de la théorie des graphes : elle consiste à affecter une couleur à chaque sommet d'un graphe simple (sans boucle ni arêtes multiples) de telle façon que deux sommets adjacents, c'est-à-dire reliés par une arête, reçoivent des couleurs distinctes. Le nombre chromatique d'un graphe est alors le nombre minimal de couleurs nécessaires pour réaliser une telle coloration. Le théorème de Brooks fournit une borne sur le nombre chromatique en fonction du degré maximal du graphe : pour tout graphe connexe qui n'est ni un graphe complet ni un cycle impair, le nombre chromatique est au plus égal au degré maximal.
Sommaire
Ce que vous allez apprendre
- Distinguer une coloration propre du minimum appelé nombre chromatique.
- Prouver que le graphe maison a pour nombre chromatique 3 avec deux bornes concordantes.
- Relier le nombre chromatique au degré maximal grâce au théorème de Brooks.
- Identifier les graphes complets et les cycles impairs comme exceptions.
- Traiter correctement les boucles et les graphes non connexes.
En clair
Imaginez cinq points reliés qui dessinent une maison : un carré, son toit et l'arête horizontale sous le toit. Deux points reliés ne doivent jamais porter la même couleur. Le triangle du toit oblige à employer trois couleurs, car chacun de ses trois sommets touche les deux autres.
Trois couleurs suffisent aussi pour toute la maison. Son nombre chromatique vaut donc 3 : c'est le plus petit nombre de couleurs qui respecte tous les voisinages, et non le nombre de couleurs choisies au hasard pour un dessin particulier.
Définition
Une coloration propre des sommets d'un graphe simple attribue une couleur à chaque sommet, avec une condition : les extrémités de toute arête ont des couleurs différentes. Si G désigne le graphe, son nombre chromatique, noté χ(G), est le plus petit entier positif k pour lequel une coloration propre avec k couleurs existe. Les noms des couleurs ne comptent pas ; seule compte la partition des sommets en classes dont aucun couple n'est adjacent.
Le degré d'un sommet est le nombre de ses voisins. Le degré maximal du graphe G, noté Δ(G), est le plus grand de ces degrés. Le théorème de Brooks affirme que, si G est connexe et n'est ni un graphe complet ni un cycle de longueur impaire, alors . Les deux exclusions sont nécessaires : ces familles peuvent demander Δ(G) + 1 couleurs.
Pour un graphe non connexe, les composantes connexes peuvent réutiliser les mêmes couleurs. Le nombre chromatique du graphe est donc le maximum des nombres chromatiques de ses composantes. Les arêtes multiples ne changeraient pas la contrainte entre deux sommets, mais la définition source se place dans le cadre des graphes simples.
De quoi c'est fait
Le calcul repose sur cinq éléments. Les sommets sont les objets à colorer. Les arêtes indiquent les couples en conflit et définissent ainsi l'adjacence. Une palette fournit les couleurs disponibles. Une coloration propre associe une couleur à chaque sommet tout en respectant chaque arête. Enfin, la minimalité compare toutes les colorations propres possibles pour retenir la plus petite palette.
Modifier une arête peut donc modifier les contraintes, puis le minimum. En revanche, déplacer un sommet sur la page, courber une arête ou renommer une couleur ne change pas le graphe ni son nombre chromatique. La liste des sommets et des arêtes suffit à tester une coloration ; prouver la valeur de χ(G) exige en plus une borne inférieure et une coloration qui atteint cette borne.
Un exemple, pas à pas
Considérons les sommets A, B, C, D et E. Les six arêtes sont AB, BC, CD, DA, BE et CE : A-B-C-D forme un carré, tandis que B-C-E forme le triangle du toit. Les degrés de A, B, C, D et E valent respectivement 2, 3, 3, 2 et 2 ; le degré maximal vaut donc 3.
1. Le triangle B-C-E impose trois couleurs distinctes. Toute coloration propre du graphe utilise donc au moins trois couleurs : χ(G) ≥ 3.
2. Attribuons le rouge à B et D, le jaune à A et C, puis le noir à E. La figure rend visibles ces cinq attributions et les six arêtes à contrôler.
3. Chaque arête relie deux couleurs différentes : AB, BC, CD et DA alternent rouge et jaune ; BE relie rouge et noir ; CE relie jaune et noir. Cette coloration propre donne χ(G) ≤ 3.
4. Les deux bornes coïncident, donc χ(G) = 3. En contrôle supplémentaire, ce graphe est connexe, n'est ni complet ni réduit à un cycle impair ; le théorème de Brooks confirme χ(G) ≤ Δ(G) = 3.
En pratique
Pour vérifier une coloration proposée, parcourez les arêtes une par une. Une seule arête dont les deux extrémités ont la même couleur suffit à invalider la proposition ; sinon, le nombre de couleurs utilisées fournit une borne supérieure de χ(G).
Pour montrer qu'une palette plus petite est impossible, cherchez une structure contraignante. Un sous-graphe complet à k sommets oblige à employer k couleurs distinctes. Dans le graphe maison, le triangle fournit ainsi la borne inférieure 3 ; sans une telle preuve, une coloration à trois couleurs ne garantit pas que 3 soit minimal.
Pour exploiter le théorème de Brooks, contrôlez d'abord la connexité, le degré maximal et les deux exceptions. Si le graphe est complet ou s'il s'agit d'un cycle impair, calculez directement son nombre chromatique ; s'il est non connexe, raisonnez composante par composante.
À ne pas confondre
Une coloration et le nombre chromatique. Une coloration est une attribution particulière de couleurs ; le nombre chromatique est le minimum parmi toutes les colorations propres. Le graphe maison peut être colorié proprement avec quatre couleurs, mais une coloration à trois couleurs prouve que son nombre chromatique n'est pas 4.
Coloration des sommets et coloration des arêtes. Ici, les sommets reçoivent les couleurs et une arête compare ses deux extrémités. Dans une coloration des arêtes, ce sont les arêtes qui sont colorées et deux arêtes ayant une extrémité commune doivent différer. Le critère testable porte donc sur des objets différents.
Limites et pièges
Graphe complet. Dans un graphe complet à n sommets, tous les sommets sont deux à deux adjacents. Il faut n couleurs, tandis que le degré maximal vaut n − 1 : on obtient χ(G) = Δ(G) + 1. C'est pourquoi cette famille est exclue de la conclusion usuelle du théorème de Brooks.
Cycle impair. Un cycle de longueur impaire ne peut pas alterner seulement deux couleurs jusqu'à son point de départ. Il demande trois couleurs, alors que chaque sommet a degré 2 : ici encore, χ(G) = 3 = Δ(G) + 1. Un cycle de longueur paire, lui, se colore avec deux couleurs.
Boucle. Une boucle rend un sommet adjacent à lui-même. La règle exigerait alors que sa couleur diffère d'elle-même, ce qui est impossible. Il faut donc rester dans le cadre des graphes sans boucle indiqué par la définition, plutôt que d'attribuer artificiellement un nombre chromatique fini.
Graphe non connexe. Appliquer Brooks au graphe entier sans examiner ses composantes masque les exceptions. Une composante complète ou un cycle impair peut imposer une couleur de plus que son degré maximal. Il faut calculer ou borner chaque composante, puis prendre le plus grand résultat.
Pour aller plus loin
coloration d'un graphe — Approfondir l'attribution des couleurs et les contraintes d'adjacence dont le nombre chromatique mesure le minimum.
Graphe complet — Examiner l'une des deux familles exceptionnelles du théorème de Brooks, où chaque paire de sommets est adjacente.
graphe biparti — Relier une partition en deux ensembles indépendants à l'existence d'une coloration propre avec deux couleurs.
degré d'un sommet d'un graphe — Détailler la quantité locale dont le maximum intervient dans la borne de Brooks.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres