Title: Clique, Stable Set and Chromatic Number

Speaker: BOUSQUET, Nicolas (GERAD & McGill University, Canada)

Abstract:
In 1987, Gyarfas introduced the concept of chi-bounded classes for the study of perfect graphs. A (closed under induced subgraphs) class C is chi-bounded if the chromatic number of any graph of C can be bounded by a function of the size of its maximal clique. Many graph classes are (perfect graphs, Pk-free graphs) or are conjectured to be (graphs with no long induced cycles, with no fixed tree...) chi-bounded. However many conjectures remain since these problems are difficult to handle. In this presentation we will focus on two problems related to chi-bounded classes which are interested by their own. One of them is the Erdos-Hajnal conjecture stating that every H-free graphs admit a clique or a stable set of polynomial size. The other is a conjecture of Yannakakis on the number of partitions of the graph which is necessary to separate cliques and stable sets. During the presentation, I will underline the links between these conjectures, recent improvements and general methods to tackle them.