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
Abstract:
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.