Programme de coloration de graphe ?

Vecteur Libre

Bonjour,
Un membre de la direction de mon établissement aimerait un coup de main pour faire le planning des DS. Elle aimerait que plusieurs épreuves différentes puissent se dérouler en même temps, sachant que pour les langues, options et "majeures", beaucoup d'élèves n'ont plus les mêmes matières.
Or le problème, une fois qu'il est bien posé, revient à colorer un graphe avec le minimum de couleurs. Je sais qu'il existe des algorithmes relativement performants sur ce problème (bien qu'il soit NP-complet) et je m'attendais à trouver assez facilement des programmes gratuits qui le fassent. Mais je n'ai vu que des TP d'étudiants qui probablement feraient l'affaire, sauf pour le côté ergonomique car ce programme devrait être facilement utilisé par des non-spécialistes (celle qui l'a demandé est prof d'anglais). Les problèmes d'emploi du temps sont courants, donc je pensais qu'il existerait beaucoup de solutions.
Ma question est donc celle-ci : connaissez-vous un programme facile d'utilisation, ergonomique etc qui calcule la solution optimale (ou une solution raisonnable) au problème de coloration de graphe ?

Romyna

Eléments de théorie des graphes Coloration de graphes Chemins de moindre coût.