Valentin Bouquet

Cette thèse porte sur des problèmes et des questions de la théorie et de l'algorithmique de graphe. La première partie concerne l'étude de l'ensemble dominant minimum. Nous considérons son problème de décision et montrons que le nombre de domination peut être déterminé en temps polynomial dans la classe des graphes sans griffe et sans chemin induit de taille au plus huit. Ensuite, nous étudions les sommets à l'intersection de tous les ensembles dominants minimums d'un graphe. Nous montrons notamment que pour certaines classes de graphes, ces sommets sont toujours critiques relativement au nombre de domination. Nous finissons cette partie sur l'étude des arêtes critiques, textit{i.e.} les arêtes dont la suppression fait varier le nombre de domination. Nous montrons dans un premier temps une borne optimale sur la cardinalité minimum d'un ensemble d'arêtes critiques dans les graphes triangulés. Dans un second temps, nous montrons qu'il est difficile de décider si il existe une arête critique dans des sous classes des graphes planaires. La seconde partie porte sur des problèmes de partitionnement des sommets du graphe. 'Etant donné une partition des sommets, nous introduisons une mesure de satisfaction pour chaque sommet, qui est le rapport entre son nombre de voisins dans sa communauté et le nombre total de ses voisins. Nous posons ensuite le problème suivant: quel est le ratio maximum a/b tel qu'un graphe possède une partition o`u chaque sommet à une satisfaction d'au moins a/b ? Nous étudions les valeurs minimums que ce critère de satisfaction peut atteindre dans différentes classes de graphes. Nous montrons aussi que ce problème est lié au problème du couplage-disconnectant dans les graphes réguliers. Pour cette raison nous poursuivons cette thèse sur l'étude du problème du couplage parfait-disconnectant. Celui-ci consiste à décider si un graphe possède une couplage parfait qui contient une coupe. Nous montrons la complexité de ce problème, notamment dans des classes de graphes planaires; de degré fixé; bipartis; de diamètre au plus d; sans-griffe; sans-P_5.

PERFECT MATCHING‐CUT is the problem of deciding whether a graph has a perfect matching that contains an edge‐cut. We show that this problem is NP‐complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite five‐regular graphs, for graphs of diameter three, and for bipartite graphs of diameter four. We show that there exist polynomial‐time algorithms for the following classes of graphs: claw‐free, ‐free, diameter two, bipartite with diameter three, and graphs with bounded treewidth.