CoSP School on homomorphisms

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