Explorateur de coloration de graphes

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.

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.

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.