coloration de graphe

En théorie des graphes, colorer un graphe signifie attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. Est souvent recherchée l'utilisation d'un nombre minimal de couleurs, dit nombre chromatique. Ce problème peut être complexifié en ne cherchant plus une mais plusieurs couleurs par sommets et en associant des coûts à chacune des couleurs. Le champ d'applications de la coloration de graphe couvre notamment le problème de l'attribution de fréquences dans les télécommunications ou la conception de puces électroniques.