***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Yukai Tang (Princeton, ORFE)

Thursday 12th February, 3:00 in Fine Hall 224.

Title: A polynomial-time combinatorial algorithm for coloring perfect graphs

We present the first polynomial-time combinatorial algorithm for
coloring perfect graphs. At its core, our algorithm decides whether
a perfect graph has a clique of a given size by counting walks on
certain weighted graphs constructed from the original graph. We
prove the correctness of our algorithm using a Lyapunov function
argument. Joint work with Amir Ali Ahmadi (Princeton, ORFE) and
Pravesh Kothari (Princeton, COS).

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)