Auteur
MECHEBBEK, Meriem
Directeur de thèse
Ait Haddadene, Hacène (Professeur)
Filière
Mathématiques
Diplôme
Doctorat
Titre
Étude structurelle de quelques classes de graphes
Mots clés
Graphes, Théorie des ; Graphes parfaits ; Coloriage des graphes
Résumé
Afin de résoudre efficacement les problèmes algorithmiques sur les graphes, il est très important de connaître les propriétés structurelles des graphes étudiés. Nous nous intéressons dans cette thèse aux aspects théorique et algorithmique de deux classes de graphes, la classe connue des graphes parfaits et celle, beaucoup plus récente, des graphes b-parfaits. La plupart des paramètres de graphes liés à la coloration, comme c'est le cas du nombre chromatique, tendent à minimiser le nombre de couleurs utilisées. D'autres paramètres tendent au contraire à maximiser ce nombre, c'est le cas du nombre b-chromatique. Tout graphe dont les nombres chromatique et b-chromatique sont égaux peut être coloré de façon optimale en temps linéaire, d'où l'intérêt des graphes b-parfaits. Comme les graphes parfaits, toute classe de graphes héréditaire peut être caractérisée par une famille (qui peut être infinie) de graphes interdits. Dans cette optique, Hoàng, Maffray et Linhares Sales ont proposé une conjecture visant à caractériser la classe des graphes b-parfaits par une liste finie de sous-graphes interdits. Nous avons abordé cette conjecture en la montrant d'abord pour la classe des graphes triangulés. Notre contribution, dans le cadre de cette thèse, est la preuve de la conjecture dans le cas général. En conséquence de ce résultat, les graphes b-parfaits peuvent être reconnus en temps polynomial. Nous proposons également un algorithme récursif polynomial pour la recherche d'une clique maximum dans tout graphe b-parfait.
Date de soutenance
21/02/2013
Cote
511.5
Pagination
108 p.
Illusatration
ill.
Format
30 cm.
Notes
Support papier accompagné d'un CD-Rom ; Bibliogr. p. 106-108
Statut
Traitée