Sujet : Colorations circulaires : algorithmes pour les allocations de ressources

Responsable : André Raspaud, Arnaud Pêcher
Téléphone : 05 56 84 88 12
e-mail : raspaud@labri.fr, pecher@labri.fr
Equipe : Combinatoire et algorithmique

Présentation du sujet :

Résumé: les problèmes de coloration sont au coeur de la théorie des graphes, et font l'objet, à ce titre, de nombreuses recherches. Le nombre circulaire chromatique d'un graphe est un paramètre plus précis que le nombre chromatique usuel. Il a été l'objet de nombreuses études depuis son introduction, il y a une quinzaine d'années. La connaissance du nombre chromatique circulaire permet d'obtenir une solution optimale à de nombreux problèmes d'allocations de ressource. En 2000, Xuding Zhu a introduit à partir de ce paramètre la classe des graphes circulaires parfaits, contenant tous les graphes parfaits.


Cette thèse sera consacrée à la mise au point d'algorithmes pour le calcul ou la majoration du nombre circulaire chromatique, ainsi qu'à l'algorithmique des graphes circulaires parfaits.


Sujet complet en pdf

Mot-clés : algorithmique, allocation de ressource, coloration de graphe, coloration circulaire