|
MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTERéduction de graphe pour la multicoloration propre
par Jean-Christophe Godin
| Date : | 23/04/08 | | Location : | Euler Bleu |
Suite aux travaux de F. Havet (2001) sur la conjecture de McDiarmid et Reed (1997), relatif à l'étude d'un modèle concernant l'allocation de fréquences dans un réseau cellulaire des télécommunications, nous avons commencé une étude de la multicoloration propre de ces graphes. Après une série de généralisations, il est apparut que les nouveaux outils développés pour résoudre cette classe particulière de problèmes, sont en fait des algorithmes de complexité quadratique, concernant la réduction des graphes pondérés pour la multichoisissabilité propre. Comme ces techniques de réduction de graphe sont à l'origine spécialisées pour la conjecture de McDiarmid et Reed (tout sous graphe induit sans triangle du réseau triangulaire est (9,4)-colorable), on déterminera dans une première partie de l'exposé, leurs efficacités pour ce problème. D'abord en démontrant un théorème qui généralise le théorème de Havet (tout sous graphe induit sans triangle du réseau triangulaire est (7,3)-colorable), ensuite on montrera que plus de 99,99..% des cas de cette conjecture sont résolus. Pour la seconde partie de l'exposé, on examinera leurs efficacités pour la choisissabilité. Comme c'est une généralisation de la coloration, il est naturel qu'ils perdent en rendement. On montrera quand même que ces sous graphes sont (5,2)-choisissable. Dans la dernière partie de l'exposé, on examinera les graphes totalement réductibles, ce qui permet de calculer leurs nombres chromatiques, leurs nombres chromatiques fractionnaires, puis leurs généralisations à la choisissabilité (nombre de choix, rapport de choix) et à la libre- choisissabilité (nombre de libre-choix, rapport de libre-choix). On démontrera un nouveau théorème qui donne une condition nécéssaire et suffisante pour qu'un cycle de longueur n soit (a,b)-libre-choisissable. Ce qui induira en corollaire un résultat similaire pour les forêts de cycles. En conclusion, on pourra étendre la résolution aux forêts de graphe O(i,j,k) pour presque toutes les valeurs, et on énoncera une série de conjectures (qui apparaissent maintenant naturellement pour des graphes plus complexes) en perspective.
Page des séminaires
|
