Abstract FR:

La thèse porte sur des problèmes de complexitè liés à des opération de décomposition de graphes. Etant donné un graphe donné H (clique, stable, biparti, graphe à seuil) et un graphe G n-apparié, on étudie la complexité algorithmique du problème suivant : Existe-t-il un sous-graphe induit de G qui contient exactement un sommet de chacune des n paires de G isomorphe à H?. On montrera enfin que le problème de décomposition des graphes appelés graphes Stubborn est équivalent au problème précédent pour un cas particulier de graphes n-appariés.