Abstract FR:

Dans ce mémoire, nous nous intéressons à deux notions de coloration sous contraintes -- coloration acyclique par listes et coloration (d,1)-totale -- ainsi qu'à un problème de conception de réseaux embarqués tolérants aux pannes. Les notions de coloration acyclique par listes et de coloration (d,1)-totale sont des notions récentes (2002). Nous apportons de nouveaux résultats concernant le calcul du nombre chromatique acyclique de listes et du nombre (d,1)-total de certaines familles de graphes (graphes de degré borné, graphes de degré moyen maximum donné,. . . ) ainsi que de nouvelles perspectives de recherche. La fiabilité des réseaux embarqués dans les satellites de télécommunication, maillons essentiels dans la chaîne de la diffusion d'information, est un enjeu important. Comment concevoir des réseaux embarqués à faible coût capables de tolérer un certain nombre de pannes et de continuer à propager l'information ? Nous donnons des éléments de réponse à cette problématique posée par Alcatel Space Industries en présentant des réseaux de coût minimal supportant un nombre de pannes donné.