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. |