Coloration généralisée des sommets avec somme minimale dans les graphes bloc
Mario Valencia-Pabon, LIPN - Université Paris-Nord

Dans cet exposé, on introduit le problème de la coloration généralisée des sommets avec somme minimum (que l'on appellera problème CGSM ) lequel consiste en affecter un ensemble d'entiers positifs de taille w(v) à chaque sommet v d'un graphe de sorte que l'intersection des ensembles affectés à toute couple des sommets adjacents soit vide et tel que la somme des entiers affectés aux sommets du graphe soit minimisée. Ce problème généralise celui classique sur la coloration des sommets avec somme minimum, lequel peut être résolu en temps polynomial pour les graphes bloc. On analysera deux versions du problème CGSM (avec préemption et sans préemption) dans deux sous-classes des graphes bloc : les arbres et les graphes représentatifs des arêtes des arbres. On montrera que les deux versions de ce problème sont NP-complets dans les graphes bloc. On montrera aussi l'existence d'algorithmes (pseudo)polynomiaux pour ce problème dans les graphes bloc si l'on fixe certains paramètres du graphe.
Travail en collaboration avec Flavia Bonomo et Guillermo Duran (Université de Buenos Aires, Argentine) et Javier Marenco (Université Nationale de Général Sarmiento, Argentine).