Evènement pour le groupe Séminaire du LaBRI

Date 2006-11-16  14:00-15:00
TitreBeyond Perfection: On Characterizations and Superclasses. 
RésuméPerfect graphs constitute a well-studied graph class with a rich structure. This is reflected by characterizations of perfect graphs with respect to such different concepts as coloring properties, the integrality of certain polyhedra, or splitting graph entropies. In addition, several otherwise NP-hard combinatorial optimization problems can be solved for perfect graphs in polynomial time. Thus, perfect graphs play a particular role in such various mathematical disciplines as graph theory, combinatorial optimization, integer and semidefinite programming, polyhedral and convexity theory, and even information theory, thereby linking those disciplines in a truly unexpected way. We present some of these concepts and their relations. Unfortunately, most graphs are imperfect and do not have such nice properties. It is, therefore, natural to ask which graphs are close to perfection in some sense and how to measure that. A canonical way is to relax several concepts which characterize perfect graphs and to investigate resulting superclasses of perfect graphs. In this talk, we consider more general coloring concepts and classes of $chi$-bound graphs, the stable set polytope and its canonical LP-relaxation, and different levels of the additivity for the graph entropy. As a common way to measure perfection w.r.t. all these concepts we present the imperfection ratio: it reflects the quality of coloring properties, the difference between the stable set polytope and its LP-relaxation, as well as additivity for the graph entropy, thereby linking the different concepts of relaxing perfectness. 
LieuAmphi 050 
OrateurAnnegret Wagler 

Aucun document lié à cet événement.

Retour à l'index