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


Date: Thursday 8th December, 3:00 in Fine Hall 224.
 
Speaker: Sergey Norin (McGill)

Title: Improperly coloring K_t minor-free graphs

We show that for every t > 0 there exists a constant c=c(t) such that, if a
graph G does not contain K_t as a minor, then its vertex set can be partitioned
into at most t-1 parts such that every part induces a subgraph with maximum
component of size at most c. This relaxation of Hadwiger's conjecture improves
previous results of Kawarabayashi and Mohar, Wood, and Liu and Oum, who proved
that the same conclusion holds for partitions into 31t/2, 7t/2 and 3t parts
respectively.  We also discuss applications of our results to extremal questions
on bootstrap percolation for minor-closed graph families. Based on joint work
with Zdenek Dvorak.

                       -----------

Next week: Mustazee Rahman

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