Résumé en français

Dans un graphe non orienté, le Problème de Coloration de Graphe (PCG) consiste à assigner à chaque sommet du graphe une couleur de telle sorte qu'aucune paire de sommets adjacents n'aient la même couleur et le nombre total de couleurs est minimisé. DSATUR est un algorithme exact efficace pour résoudre le PCG. Un de ses défauts est qu'une borne inférieure est calculée une seule fois au noeud racine de l'algorithme de branchement, et n'est jamais mise à jour. Notre nouvelle version de DSATUR surpasse l'état de l'art pour un ensemble d'instances aléatoires à haute densité, augmentant significativement la taille des instances résolues. Nous étudions trois formulations PLNE pour le Problème de la Somme Chromatique Minimale (PSCM). Chaque couleur est représentée par un entier naturel. Le PSCM cherche à minimiser la somme des cardinalités des sous-ensembles des sommets recevant la même couleur, pondérés par l'entier correspondant à la couleur, de telle sorte que toute paire de sommets adjacents reçoive des couleurs différentes. Nous nous concentrons sur l'étude d'une formulation étendue et proposons un algorithme de Branch-and-Price.