Coloration bornée avec multiplicité

Abstract

<p> Nous nous intéressons à des graphes avec multiplicités sur les sommets. Ces graphes permettent de modéliser de manière compacte des problèmes dans lesquels il existe des relations entre différentes classes contenant des éléments identiques. En particulier, nous nous intéressons au problème coloration bornée sur ces graphes : comment colorer les sommets du graphe (en donnant autant de couleurs à un sommet que sa multiplicité) de telle sorte que deux sommets adjacents n'aient aucune couleur en commun et que le nombre de sommets d'une même couleur soit borné ?</p> <p>Ce problème est inspiré du problème de placement unidimensionnel cutting-stock : comment ranger de manière efficace un ensemble d'objets dans des boîtes de taille fixée ? Chaque objet i doit être rangé b(i) fois. Dans cette variante, les objets ont tous la même taille mais certains ne peuvent être rangés ensemble. Il est possible de modéliser ce problème par un problème de coloration bornée sur un graphe où l'on crée pour chaque objet i, b(i) sommets jumeaux. Dans ce cas, le graphe obtenu ne dépend plus polynomialement de la taille de la donnée initiale. Il est donc plus efficace de représenter le nombre d'objets de chaque type par un sommet de multiplicité b(i).</p> <p>Nous donnons une formulation compacte des solutions de ce problème en utilisant des ensembles stables maximaux. Puis nous montrons que ce problème est NP-complet pour des unions de cliques disjointes mais résolvable en temps polynomial pour les complémentaires de graphes triangulés.</p>