Carl-Johan Casselgren: Coloring graphs from random lists

The topic of this talk is list colorings of graphs. In this model each vertex of a graph is assigned a list (set) of colors and the task is then to construct a proper coloring of the graph such that each vertex gets a color from its list. I will review some basic facts about list coloring and then discuss a variation on list coloring where each vertex receives a random list: let G=G(n) be a graph on n vertices, and assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all k-subsets of a color set of size σ(n). I will discuss various conditions which imply that, with probability tending to 1 as n goes to infinity, G has a proper coloring from the random lists.