Soutenance de thèse de Yohann Benchetrit le mardi 12-05-15 à 14h30 en amphi Gosse à Grenoble INP

Titre: Propriétés géométriques du nombre chromatique: polyèdres, structure et algorithmes

Membres du Jury:

Résumé:
Le calcul du nombre chromatique et la détermination d’une coloration optimale des sommets d’un graphe sont des problèmes NP-difficiles en général. Ils peuvent cependant être résolus en temps polynomial dans les graphes parfaits. Par ailleurs, la perfection d’un graphe peut être décidée efficacement. Les graphes parfaits sont caractérisés par la structure de leur polytope des stables : les facettes non-triviales sont définies exclusivement par des inégalités de cliques. Réciproquement, une structure similaire des facettes du polytope des stables détermine-t-elle des propriétés combinatoires et algorithmiques intéressantes ? Un graphe est h-parfait si les facettes non-triviales de son polytope des stables sont définies par des inégalités de cliques et de circuits impairs. On ne connaît que peu de résultats analogues au cas des graphes parfaits pour la h-perfection, et on ne sait pas si les problèmes sont NP-difficiles. Par exemple, les complexités algorithmiques de la reconnaissance des graphes h-parfaits et du calcul de leur nombre chromatique sont toujours ouvertes. Par ailleurs, on ne dispose pas de borne sur la différence entre le nombre chromatique et la taille maximum d’une clique d’un graphe h-parfait. Dans cette thèse, nous montrons tout d’abord que les opérations de t-mineurs conservent la h-perfection (ce qui fournit une extension non triviale d’un résultat de Gerards et Shepherd pour la t-perfection). De plus, nous prouvons qu’elles préservent la propriété de décomposition entière du polytope des stables. Nous utilisons ce résultat pour répondre négativement à une question de Shepherd sur les graphes h-parfaits 3-colorables. L’étude des graphes minimalement h-imparfaits (relativement aux t-mineurs) est liée à la recherche d’une caractérisation co-NP combinatoire de la h-perfection. Nous faisons l’inventaire des exemples connus de tels graphes, donnons une description de leur polytope des stables et énonçons plusieurs conjectures à leur propos. D’autre part, nous montrons que le nombre chromatique (pondéré) de certains graphes h-parfaits peut être obtenu efficacement en arrondissant sa relaxation fractionnaire à l’entier supérieur. Ce résultat implique notamment un nouveau cas d’une conjecture de Goldberg et Seymour sur la coloration d’arêtes. Enfin, nous présentons un nouveau paramètre de graphe associé aux facettes du polytope des couplages et l’utilisons pour donner un algorithme simple et efficace de reconnaissance des graphes h-parfaits dans la classe des graphes adjoints.

Abstract :
Computing the chromatic number and finding an optimal coloring of a perfect graph can be done efficiently, whereas it is an NP-hard problem in general. Furthermore, testing perfection can be carried-out in polynomial-time. Perfect graphs are characterized by a minimal structure of their stable set polytope: the non-trivial facets are defined by clique-inequalities only. Conversely, does a similar facet-structure for the stable set polytope imply nice combinatorial and algorithmic properties of the graph ? A graph is h-perfect if its stable set polytope is completely described by non-negativity, clique and odd-circuit inequalities. Statements analogous to the results on perfection are far from being understood for h-perfection, and negative results are missing. For example, testing h-perfection and determining the chromatic number of an h-perfect graph are unsolved. Besides, no upper bound is known on the gap between the chromatic and clique numbers of an h-perfect graph. Our first main result states that the operations of t-minors keep h-perfection (this is a non-trivial extension of a result of Gerards and Shepherd on t-perfect graphs). We show that it also keeps the Integer Decomposition Property of the stable set polytope, and use this to answer a question of Shepherd on 3-colorable h-perfect graphs in the negative. The study of minimally h-imperfect graphs with respect to t-minors may yield a combinatorial co-NP characterization of h-perfection. We review the currently known examples of such graphs, study their stable set polytope and state several conjectures on their structure. On the other hand, we show that the (weighted) chromatic number of certain h-perfect graphs can be obtained efficiently by rounding-up its fractional relaxation. This is related to conjectures of Goldberg and Seymour on edge-colorings. Finally, we introduce a new parameter on the complexity of the matching polytope and use it to give an efficient and elementary algorithm for testing h-perfection in line-graphs.