Combinatorics Seminar

When: Sunday, November 23, 10am
Where: Schreiber 309
Speaker: Rogers Mathew, Caesarea Rothschild Institute, University of Haifa
Title: On the partial list coloring conjecture


Let l_k be an arbitrary function that assigns each vertex of a graph G a list of k colors. Then G is l_k-list colourable if there exists a proper coloring of the vertices of G such that every vertex is colored with a colour from its own list. We say G is k-choosable if for every such function l_k, G is l_k-list colorable. The minimum k such that G is k-choosable is called the list chromatic number of G.

Let the list chromatic number of G be s, and let t be a non-negative integer such that t<=s. Let n denote the number of vertices of G. The partial list coloring conjecture due to Albertson et al. [1] states that for every function l_t that maps the vertices of G to t-sized lists, there always exists an induced subgraph of G of size at least (t*n/s) that is l_t-list colorable. In this talk, we give an outline of the various small progresses made so far towards resolving this conjecture.

References [1] Michael O Albertson, Sara Grossman, and Ruth Haas. Partial list colorings. Discrete Mathematics, 214(2000), 235-240.