Group for Research in Decision Analysis

Clique, Stable Set and Chromatic Number

Nicolas Bousquet McGill University, Canada

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.