GSCOP-RUB-OC-poster

Soutenance de thèse de Cléophée ROBIN (OC) vendredi 22 octobre 2021 à 14h en amphi Barbillon - Grenoble INP 46 Avenue Félix Viallet

Intitulée : Classes héréditaires de graphes : De la structure vers la coloration.

Les membres du jury :
 
  • Pierre Charbit, Maître de conférence, Université de Paris, Rapporteur,
  • Daniel Paulusma, Professeur, Durham University, Rapporteur,
  • Nadia Brauner, Professeure, Université Grenoble Alpes, Examinatrice,
  • Eunjung Kim, Chargée de recherche, CNRS, Examinatrice,
  • Myriam Preissmann, Directrice de recherche, CNRS, Directrice de thèse,
  • Nicolas Trotignon, Directeur de recherche, CNRS, Directeur de thèse.

Le résumé :


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.


Abstact :

This thesis deals with the structure of some hereditary classes of graphs. A class of graphs is hereditary if it is characterized by a set of forbidden induced subgraphs. A better understanding of the structure of graphs contained in such classes sometimes yields algorithmic results on optimisation problems that are NP-complete in the general case. We particularly focused on the vertex coloring problem of a graph (or its complement). Through this defense, we will present some results from the thesis.


The prismatic graphs are the graphs without clique of size 4, diamond, or the complement of a claw as induced subgraph. Their structure was fully described by Chudnovsky and Seymour that divided the class into two subclasses : the orientable prismatic graphs and the non-orientable prismatic graphs. In the defense, we will present the following results:
A non-orientable prismatic graph has at most 10 disjoint triangles.
An O(n7.5)-time algorithm that solves the clique covering problem for non-orientable prismatic graphs.
An O(n5)-time algorithm that solves the maximum disjoint triangles problem for both orientable and non-orientable prismatic graphs.

Given k≥4, the class Ck is the set of graphs whose holes all have length k. This class contains the class of chordal graphs and is contained in the class of even-hole-free graphs. We will describe the "blowup of templates" and we will give the following characterization for graphs in Ck for odd k≥7:
A graph in Ck without clique cutset nor universal vertex, is either a ring or a blowup of template.