Coloring some perfect graphs

Perfect graphs are a class of graphs that behave particularly well with respect to coloring. In the 1960's Claude Berge made two conjectures about this class of graphs, that motivated a great deal of research, and by now they have both been solved.

The following remained open however: design a combinatorial algorithm that produces an optimal coloring of a perfect graph. Recently, we were able to make progress on this question, and we will discuss it in this talk. Last year, in joint work with Lo, Maffray, Trotignon and Vuskovic we were able to construct such an algorithm under the additional assumption that the input graph is square-free (contains no induced four-cycle). More recently, together with Lagoutte, Seymour and Spirkl, we solved another case of the problem, when the clique number of the input graph is fixed (and not part of the input).