Explorateur de coloration de graphes

Faites glisser des sommets, dessinez des arêtes et coloriez le graphe à la main ou avec un algorithme glouton — observez comment la borne inférieure par clique révèle le nombre de couleurs réellement nécessaires.

Exemple résolu — Explorateur de coloration de graphes

Sommets	3
Arêtes	3
Couleurs utilisées	0
Conflits	0

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

combien de couleurs vous faut-il vraiment ? 🖖

Le nombre chromatique χ(G) est le nombre minimal de couleurs nécessaire pour qu'aucune arête ne relie deux sommets de même couleur. Le calculer exactement est NP-difficile — la meilleure garantie générale se situe entre une borne inférieure par clique (toute clique de taille k impose au moins k couleurs) et une borne supérieure gloutonne (la coloration de Welsh-Powell, par degré décroissant, n'utilise jamais plus de Δ+1 couleurs, où Δ est le degré maximal). Pour les graphes planaires — ceux que l'on peut dessiner sans croisement d'arêtes — le théorème des quatre couleurs garantit que 4 couleurs suffisent toujours ; il a été prouvé pour la première fois par ordinateur en 1976 et reste l'un des rares théorèmes majeurs nécessitant une vérification exhaustive des cas par ordinateur. La coloration de graphes sous-tend de vrais problèmes d'affectation : l'allocation de registres dans les compilateurs, la planification d'examens et l'attribution de fréquences radio se ramènent tous à la coloration d'un graphe de conflits.

les voisins doivent différer — voilà tout l'enjeu 🖖

La coloration de graphes se résume à une règle : aucune arête ne peut relier deux sommets de même couleur, et l'on cherche à utiliser le moins de couleurs possible. Cette seule contrainte décide de tout. Un test pratique : tout cycle de longueur paire se colore avec 2 couleurs, mais tout cycle de longueur impaire en exige 3 — un triangle (le plus petit cycle impair) ne peut donc jamais être colorié avec 2 couleurs. Construisez les deux dans l'outil et observez le nombre de conflits.

la coloration gloutonne peut échouer de façon spectaculaire 🖖

Colorer les sommets un à un en prenant toujours la plus petite couleur libre semble sûr, mais l'ordre compte énormément. Sur une famille appelée graphes couronne — 2n sommets ne nécessitant que 2 couleurs — un ordre malveillant force la méthode gloutonne à en utiliser n. Son pire cas est sans borne, et c'est précisément pourquoi la coloration automatique de l'outil trie les sommets par degré décroissant (Welsh-Powell) pour éviter de tels pièges.

Problèmes entièrement résolus

Le nombre chromatique réel du graphe de Petersen 5 étapes
Le graphe de Petersen compte 10 sommets, 15 arêtes et aucun triangle. Le panneau indique donc χ ≥ 2. Trouvez le nombre chromatique réel. Il s'agit de l'état Graphe de Petersen.
1. Deux bornes s'obtiennent gratuitement pour tout graphe : il nécessite au moins autant de couleurs que sa plus grande clique, et jamais plus d'une unité au-dessus de son degré maximum.
  
  $ω (G) \leq χ (G) \leq Δ (G) + 1 : Petersen has ω = 2, Δ = 3 ⟹ 2 \leq χ \leq 4$
2. La maille du graphe de Petersen vaut 5, il n'y a donc aucun triangle et la borne de la clique se réduit au cas trivial 2. C'est le nombre indiqué par le panneau.
  
  $girth = 5 ⟹ no triangle ⟹ ω = 2, yet the graph is not bipartite$
3. Deux couleurs ne sont possibles que lorsque le graphe est bipartite, et bipartite signifie l'absence de cycle impair. Le pentagone extérieur est un 5-cycle, deux couleurs sont donc à exclure.
  
  $bipartite ⟺ no odd cycle; the outer 5-cycle is odd ⟹ χ \geq 3$
4. Trois couleurs suffisent : il suffit d’exhiber une coloration pour démontrer la borne supérieure. En suivant le pentagone extérieur, attribuez à ses sommets les couleurs 1, 2, 1, 2, 3, puis aux cinq sommets intérieurs les couleurs 2, 1, 3, 3, 2 dans le même ordre, chacun étant relié au sommet extérieur situé sur son rayon. Parcourez les quinze arêtes : leurs extrémités sont toujours de couleurs différentes.
  
  $a 3-colouring exists ⟹ χ = 3, strictly above the clique bound ω = 2$
5. Le théorème de Brooks affirme la même chose par le haut : un graphe connexe qui n'est ni complet ni un cycle impair nécessite au plus Δ couleurs, et Δ vaut 3 ici.
  
  $∣ V ∣ = 10, ∣ E ∣ = 15, Δ = 3 : Brooks’ theorem gives χ \leq 3 for a connected non-complete graph$
Réponse

3, ce qui est strictement supérieur à la borne que le panneau peut prouver. La plus grande clique dans le graphe de Petersen est une arête unique, donc la borne de la clique donne seulement χ ≥ 2, et elle se trompe d'une unité. L'écart importe plus qu'il n'y paraît : Petersen est le contre-exemple classique à l'intuition selon laquelle la difficulté de coloration provient des cliques, et il existe des graphes sans triangle nécessitant quatre couleurs, cinq, ou n'importe quel nombre souhaité — la construction de Mycielski les produit à la demande. Le nombre de clique est donc une borne inférieure qui peut être arbitrairement éloignée de la réalité, ce qui explique pourquoi le problème du nombre chromatique est NP-difficile tandis que trouver un triangle ne l'est pas. Ce qui fixe la valeur exacte pour Petersen à 3, c'est un cycle impair pour la borne inférieure et le théorème de Brooks pour la borne supérieure.

$χ (Petersen) = 3 > ω = 2 : the clique bound is not tight$
Comparaison des bornes pour χ sur le graphe complet K4 5 étapes
À présent K₄ — quatre sommets, les six arêtes présentes. Calculez χ et comparez les bornes avec ce qu'elles ont donné sur Petersen. Il s'agit de l'état K4 complet.
1. Comptez les arêtes plutôt que de vous fier à l'image : chaque paire parmi quatre sommets est reliée, et il y a six paires.
  
  $K_{4} : ∣ V ∣ = 4, ∣ E ∣ = (2 4) = 6, every pair adjacent$
2. Chaque sommet est adjacent à tous les autres, donc deux sommets ne peuvent pas partager une même couleur. C'est une borne inférieure de 4 qui ne nécessite aucun autre argument que la définition.
  
  $all four vertices are mutually adjacent ⟹ ω = 4 ⟹ χ \geq 4$
3. Quatre couleurs suffisent évidemment, la borne est donc atteinte. Le même raisonnement donne χ(Kₙ) = n pour tout n, ce qui fait des graphes complets le cas facile.
  
  $four colours suffice trivially ⟹ χ (K_{n}) = n$
4. Mettez les deux graphes côte à côte. Même question, mêmes deux bornes, et l'écart entre elles constitue l'ensemble du sujet.
  
  $here ω = χ = 4 : the bound is tight, and Petersen showed it need not be$
5. Remarquez la position du théorème de Brooks ici. Sa borne de Δ = 3 serait fausse pour K₄, ce qui explique pourquoi les graphes complets en sont explicitement exclus.
  
  $Δ + 1 = 4 as well — Brooks’ theorem excludes complete graphs for exactly this reason$
Réponse

4, et ici chaque borne est atteinte simultanément. Le nombre de clique vaut 4 car le graphe entier est une clique, Δ + 1 vaut 4 car chaque sommet est relié aux trois autres, et la vraie réponse se retrouve coincée entre les deux sans échappatoire. C'est le cas sur lequel les gens construisent leur intuition, et c'est exactement le cas que le théorème de Brooks exclut — sa borne de Δ s'applique à tout graphe connexe sauf les graphes complets et les cycles impairs, et ces deux problèmes sont la raison de ces deux exceptions. Petersen et K₄ marquent les deux extrémités : l'une où la borne de la clique échoue d'une unité, l'autre où elle ne peut pas échouer du tout.

$χ (K_{4}) = ω (K_{4}) = Δ + 1 = 4$

Références (2)

Insight block 1 — the four colour theorem, and the computer proof it needed: K. Appel and W. Haken, "Every planar map is four colorable. Part I: Discharging." Illinois Journal of Mathematics 21(3), 429–490, 1977.
And the descending-degree ordering the auto-colour button uses: D. J. A. Welsh and M. B. Powell, "An upper bound for the chromatic number of a graph and its application to timetabling problems." The Computer Journal 10(1), 85–86, 1967.

Par l’équipe 42Math · Mis à jour 2026-06-16

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Informatique →

Explorateur de coloration de graphes

combien de couleurs vous faut-il vraiment ? 🖖

les voisins doivent différer — voilà tout l'enjeu 🖖

la coloration gloutonne peut échouer de façon spectaculaire 🖖

Exemples de problèmes