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


Date: Thursday 6 October, 2.15 in Fine Hall 224
 
Speaker: Eli Berger, Haifa University

Title: On the strong coloring of graphs with bounded degree.

Abstract: Let G be a graph with n vertices and let r be a number
dividing n. We say that G is strongly r-colorable if for every
partition of the vertices of G into sets of size r, there exists a
proper coloring of G in which every set in the partition is colored in
all colors. Alon was the first who showed that if r>cd then G must be
strongly r-colorable, where d is the maximum degree in the graph and c
is some constant number. This result raises the question, for a fixed
number d, what is the minimum number s(d) with the property that
every graph with maximum degree d is strongly s(d)-colorable? It is
not hard to show that s(d) is at least 2d and the natural conjecture is
s(d) = 2d. The result closest to this conjecture is Haxell's proof that
s(d) \leq 11d/4 + o(d). In this talk I will describe the arsenal of
methods used to attack this problem and show that s(2) = 4.

This is joint work with Abeer Shkerat.


                       -----------

Next week: Shachar Lovett.

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