Speaker:  Zsolt Tuza, Computer and Automation
Research Institute, Hungarian Academy of Science

Title: Restricted types of graph colorings

Abstract:
A (proper) vertex coloring of a graph is an assignment of the vertices to
colors in such a way that no two adjacent vertices get the same color.
Since the early 1990s, many papers have been published on coloring
problems where the availability of colors is locally restricted for each
vertex. In the central concept of "list coloring" a set (list)  L(v)  of
allowed colors is given for every vertex  v,  and the question is whether
there exists a proper coloring that takes the color of each  v  from its
list. In the talk we present several variants, old and new results, some
of the typical applications, and open problems.
Further information can be found in the following two surveys:

  Zs. Tuza: Graph colorings with local constraints--A survey. Discuss.
     Math. Graph Theory, 17, 1997, 161-228.
  J. Kratochvil - Zs. Tuza - M. Voigt: New trends in the theory of
     graph colorings: Choosability and list coloring. DIMACS Ser. in
     Discr. Math. and Theor. Comp. Sci. Vol. 49, 1999, 183-197.