The school consists of a series of lectures on
The Lov\'asz's theta function and perfect graphs.
by prof. Arnaud Pecher
The clique number is a trivial lower bound for the chromatic number, but
by far not always tight.
The graphs where both parameters coincide for all induced subgraphs are
called perfect. A main result of combinatorial optimization is that the
weighted clique number and the chromatic number of a perfect graph are
computable in polynomial time (Gr\"otschel, Lov\'asz and Schrijver 1981).
I will outline the proof of this celebrated result, with a focus on Lov\'asz's theta function.
The schedule of lectures:
December 3: 14:40 - 18:50 in lecture room S7
December 4: 14:00 - 17:20 in lecture room S10
Posted on 2019-11-05