| Monday, September 29nd, 2014 | 4pm-5pm | Burnside 1205 |
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 open. 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 Erd\H{o}s-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 talk, I will underline the links between these conjectures, recent improvements and general methods to tackle them.