Thèse Cléophée ROBIN

Auteur : Cléophée ROBIN
Directrice de thèse : Myriam PREISSMANN
Directeur de thèse : Nicolas TROTIGNON
Date de soutenance : 22 octobre 2021

   

Cette thèse porte sur la structure de certaines classes de graphes héréditaires. Une classe de graphes est héréditaire si elle est caractérisée par un ensemble de sous-graphes induits interdits. Une meilleure compréhension de la structure des graphes dans une telle classe peut conduire à des résultats algorithmiques pour certains problèmes d’optimisation qui sont NP-complets dans le cas général. Nous avons plus particulièrement considéré le problème de coloration des sommets d’un graphe (ou de son complémentaire). Lors de la soutenance, nous présenterons une partie des résultats obtenus durant la thèse.

Les graphes prismatiques sont les graphes qui ne possèdent comme sous-graphe induit ni clique de taille 4, ni diamant, ni le complément d’une griffe. Leur structure a été intégralement décrite par Chudnovsky et Seymour qui les séparent en deux catégories : les orientables et les non-orientables. Durant la soutenance, nous présenterons les résultats suivants :

• Tout graphe prismatique non-orientable possède au plus 10 triangles disjoints.
• Un algorithme en O(n7.5) qui résout le problème de la couverture par cliques pour les graphes prismatiques non-orientables.
• Un algorithme en O(n5) qui résout le problème du nombre maximum de triangles disjoints pour les graphes prismatiques, tant orientables que non-orientables.

Etant donné k≥4, la classe Ck est l’ensemble des graphes dont tous les trous sont de longueur k. Notons que cette classe contient les graphes triangulés et que pour k impair, elle est contenue dans la classe des graphes sans trou pair. Nous esquisserons une description des graphes que nous avons nommés “blowup de templates” et donnerons la caractérisation suivante des graphes dans Ck pour k impair et au moins 7:

• Un graphe dans Ck qui ne contient ni clique cutset ni sommet universel est soit un ring soit un blowup de template.