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


Abstract:


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