Evénements



Calendrier

octobre 2017 :

Rien pour ce mois

septembre 2017 | novembre 2017

Coloration de graphe

Accueil > Communauté GOSPI > Thèses

Doctorant : Pastor Lucas

  • Directeur : MAFFRAY Frédéric
  • Laboratoire : G-SCOP

La coloration des sommets d’un graphe (nombre chromatique) est un des principaux problèmes de la théorie des graphes, avec de nombreuses applications dans des domaines divers (ordonnancement, télécommunications, etc). Ce problème est très difficile : il est NP-complet même dans des classes d’instances assez réduites. Une des variantes les plus étudiées (et les plus utiles) est le problème de la coloration par listes, où chaque sommet se voit restreint à une liste de couleurs autorisées, les listes pouvant être très différentes d’un sommet à l’autre. On peut aussi considérer le problème de la coloration des arêtes d’un graphe (indice chromatique), et ce problème admet lui aussi une variante par listes. Une conjecture célèbre de Vizing dit que l’indice chromatique par liste d’un graphe est égal à son indice chromatique normal. Cette conjecture peut être reformulée en termes de line- graphe (graphe représentatif des arêtes d’un graphe) et donc en un problème de coloration de sommets de ces graphes. Il est connu que tous les line-graphes appartiennent à la classe des graphes sans griffe. Une extension de la conjecture de Vizing aux graphes sans griffe a été proposée par Gravier et Maffray. Le but de cette thèse sera d’étudier ce dernier problème, en particulier pour les graphes parfaits. En effet, pour les graphes parfaits sans griffe on connait un théorème de décomposition en deux classes de bases indécomposables (les graphes péculiers et les graphes élémentaires) dont la structure est bien comprise. Le schéma de la décomposition est basé sur la clique d’articulation. Le but de la thèse sera d’étudier des problèmes structurelles, des problèmes de coloration ainsi que le comportement du nombre chromatique par liste dans chacune des classes de base et comment il évolue le long du schéma de décomposition par clique d’articulation. Une manière d’aborder ce problème consistera à l’attaquer pour les graphes où la taille maximum de la clique est bornée, en espérant augmenter cette borne autant que possible.