William Hu, Rutgers University

Abstract

List colorings are a natural generalization of classical graph colorings. Rather than coloring our graph using the same set of colors at each vertex, we assign a list of colors to each vertex, and assign each vertex a color from its corresponding list. The list coloring number, in comparison to the chromatic number, is the smallest integer n such that if we assign a list L(v) of size n to each vertex v, there exists a legal coloring f such that for every vertex v, f(v) is in L(v). As it turns out, the list coloring number cannot be bounded by the chromatic number. So what can we say about the list coloring number? In this talk we’ll consider the List Coloring Conjecture, and related open problems such as generalizing Vizing’s theorem to list colorings.