Etiquetage de graphes : codage et coloration

Abstract

Dans ce mémoire de thèse, nous nous intéressons a deux variantes d’étiquetage de graphes : l’étiquetage de distance et l’étiquetage avec contraintes tel que le L(p, q)-étiquetage et l’étiquetage (d, 1)-total. L’étiquetage de distance est un codage du graphe permettant de calculer des distances. Nous nous sommes efforces d'en définir un schéma pour les graphes de permutation. Pour cela, une étude sur la structure de cette famille a été effectuée. Dans cette optique, nous avons propose une caractérisation de cette famille et défini un algorithme de reconnaissance dynamique. La seconde partie de notre travail s'est portée sur l’étiquetage (d, 1)-total et le L(p, q)-étiquetage qui sont des problèmes liés a l'assignation de fréquences dans des réseaux d’émetteurs. Pour l’étiquetage (d, 1)-total, nous obtenons des résultats optimaux sur la largeur de la bande de fréquence utilisée dans le cas des topologies planaires de grande maille et de grand degre maximum. Enfin, pour le L(p, q)-étiquetage une étude de complexité sur des étiquetages sans trou a été effectuée. Nous donnons la complexité de la décidabilité sur cet étiquetage dans les graphes quelconques suivant les valeurs des paramètres p et q. En effet, tous les graphes n'admettent pas de L(p, q)-étiquetage sans trou, le problème de décidabilité est donc primordial