Abstract FR:

La conjecture forte des graphes parfaits est une célèbre conjecture qui est ouverte depuis près de quatre ans. On sait qu'un contre-exemple minimal éventuel à cette conjecture appartiendrait à la classe des graphes partitionnables. La motivation principale de cette thèse est de construire des graphes partitionnables inconnus à ce jour, en se basant sur une approche novatrice. Cette approche consiste à étudier des graphes de Cayley associés aux quasi-factorisations des groupes finis. Dans cette étude, nous généralisons des résultats récents publiés en 1998 et nous en présentons d'autres permettant de comprendre un peu mieux pourquoi de nombreux groupes n'ont pas de quasi-factorisation. Nous énonçons également plusieurs résultats concernant directement la conjecture forte des graphes parfaits. Certains de nos résultats permettent d'accélérer les recherches exhaustives par ordinateur. Ils ont fait l'objet d'une implantation. Les calculs que nous avons effectués, ont permis de découvrir effectivement des nouveaux graphes partitionnables qui n'appartiennent à aucun des procédés de construction de graphes partitionnables déjà publiés.