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

Speaker: Alex Scott (Oxford)

Thursday 8th November, 3:00 in Fine Hall 224.

Title: Induced trees and Erdos-Hajnal

A hereditary class of graphs has the Erdos-Hajnal property if there is some
c>0 such that every graph G in the class contains a complete graph or
independent set of size at least |G|^c. The Erdos-Hajnal Conjecture asserts
that for every graph H the class of graphs with no induced copy of H has the
Erdos-Hajnal property.  Resolving a conjecture of Liebenau and Pilipczuk,
we show that, for every forest T, the class of graphs with no induced copy 
of T or its complement has the Erdos-Hajnal property. This is joint work 
with Maria Chudnovsky, Paul Seymour and Sophie Spirkl.


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

Next week: Gal Kronenberg

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