PIMS/ UBC Distinguished Colloquium: Maria Chudnovsky

  • Date: 02/26/2016
  • Time: 15:00
Maria Chudnovsky, Princeton University

University of British Columbia


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

Other Information: 

Location: ESB 2012

A reception will be held from 2:30pm- 3:00pm at the PIMS Lounge, ESB 4133.