Title: Perfect and "Imperfect" Graphs
Speaker: Arran Hamm, Rutgers University
Date: Wednesday, March 31, 2010 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
A perfect graph is one such that for every induced subgraph, the chromatic number equals the clique number. The PGT states that a graph is perfect if and only if its complement is perfect. In this talk an elementary proof of this will be given using a bit of linear algebra. On the other hand, graphs which are far from perfect will be discussed with a probabilistic theorem of Erdos and then an elementary (yet shocking) construction of such graphs will be given.