Abstract :

The proof of perfect graph theorem is unsurpassed in its elegence and one that shows the 'feel' for the problem in designing the proof. We discuss this beautiful proof in the first talk. The second proof is another elegent linear algebra proof given by Gasparian, which we will discuss in a later lecture. A graph is perfect if the chromatic number and size of largest clique coincide for every induced subgraph. The perfect graph therem states that a graph is perfect iff its complement is perfect.