Résumé :

Le problème du couplage maximal est un problème de graphe classique, connu pour se résoudre en temps polynomial. Lorsqu'on ajoute des couleurs sur les sommets et des contraintes de couleurs sur la solution, de maximisation ou de minimisation par exemple, comment les choses évoluent-elles ?