Exposé de Vincent JOST (IMAG-LEIBNIZ)

Le but principal de l'exposé est de montrer la souplesse du paradigme alpha|beta|gamma (voir ici) pour synthétiser les théorèmes non-seulement dans d'autres domaines que l'ordonnancement, mais aussi, d'autres types de théorèmes que ceux de complexité.

A un niveau méthodologique, je crois que ce type de réflexion peut contribuer au développement et surtout à la meilleure utilisation des résultats mathématiques produits en grande quantité.

Je ne présenterai pas cette opinion de manière formelle. A la place je l'illustrerai sur un exemple.

Colorier un graphe c'est partitionner ses sommets de telle sorte qu'aucune classe de la partition contienne une arrête. En général étant donné un graphe on cherche à le colorier en utilisant le moins de couleurs possibles.

Ce problème est utile pour de nombreuses applications, toutefois il est rarement utilisable tel quel. Il faut souvent enrichir la formulation pour prendre en compte la nature du problème appliqué. Les enrichissements nécéssaires sont souvent déjà connus dans la théorie de l'ordonnancement.

Des nombreuses extensions communes de problèmes d'ordonnancement et de colorations est né le terme "ordonnancement chromatique".

Un aspect difficile du travail d'un chercheur en ordonnancement chromatique est la multitude de résultats et la difficulté de référencement de ces résultats, à tel point que certains sont périodiquement redécouverts (et republiés).

Après avoir donné quelques exemples de problèmes de l'ordonnancement chromatique avec leurs motivations applicatives, J'évoquerai une extension de la classification \alpha-\beta-\gamma à l'ordonnancement chromatique.

Je détaillerai pour cela le problème de la "coloration b-bornée" [ColB] dans lequel chaque couleur ne peut pas être utilisée plus de b fois et dans lequel on cherche à minimiser le nombre de couleurs. Je montrerai comment ce problème se place (en termes de réductions) par rapport à d'autres problèmes comme la coloration, la partition en triangles, le couplage max. Je dessinerai les frontières de compléxité et d'approximabilité en fonction du problème, de la classe de graphe et des paramètres auxquels on se restreints.

La conviction qui motive cet exposé est que ce type de synthèse mène à de profonds résultats mathématiques, que j'évoquerai si le temps le permet.

En particulier, l'inégalité de Berge-Tutte pour le couplage max et l'inégalité de clique peuvent etre généralisées en une seule inégalité pour avoir une borne inf pour [ColB]. Cette borne inf donne une formule min-max pour la coloration bornée restreinte aux compléments de graphes triangulés. (Cela généralise des résultats de Papadimitriou & Yannakakis, Bodlander & Jansen, Karpinski... plus de précisions sur ce résultat sont accessibles dans le fichier joint).