This thesis is about graph theory and more specifically enumeration algorithms for subgraphs or supergraphs. The problem we consider is the following: given a graph G and a graph property P, can we find an efficient algorithm generating exactly once all the inclusion-wise maximal (induced or not) subgraphs of G that satisfy the property P? We are interested as well in inclusion-wise minimal supergraphs of G - called minimal completions of G - verifying P.
Efficient algorithms, running with polynomial delay in polynomial space, are obtained for some of these problems when P describes the classes of split graphs, cographs, threshold graphs and chordal graphs.

Jury :
Fatiha Bendali - Université Clermont Auvergne - Examiner
Marthe Bonamy - CNRS, Université de Bordeaux - Examiner
Nofar Carmeli - Inria, Université de Montpellier - Examiner
Roberto Grossi - Università di Pisa - Referee
Christian Laforest - Université Clermont Auvergne - Examiner
Vincent Limouzy - Université Clermont Auvergne - Supervisor
Ioan Todinca - Université d'Orléans - Referee
Nicolas Trotignon - CNRS, ENS de Lyon - Examine.