Discrete Mathematics Seminar
Speaker: Bill Martin, WPI
Title: Some remarks on list coloring
ABSTRACT: I will survey a few results about graph list coloring. Graph coloring is a rich area of research and many intriguing open problems remain. In this variation, each vertex is provided a "list" of colors allowable at that vertex and one asks, for a given graph and a given collection of color lists at its vertices, whether or not a proper coloring can be found in which each vertex chooses its color from its own list. Surprises include the fact that, for every positive integer k, there exists a bipartite graph and an assignment of lists each of size k with respect to which no proper list-coloring exists. All is not lost, though, as Carsten Thomassen proved in 1994 that every planar graph admits a proper list-coloring provided each list has size five or more. While I will try to survey a few of these results, I will focus on two of my papers. The first, written with Jeff Dinitz, pursues an algebraic approach of Alon and Tarsi, especially in the case of uniquely list-colorable graphs. The second is a recent non-refereed paper describing an example discovered by the late Fields Medalist Maryam Mirzakhani when she was very young. The talk should be mostly accessible to undergraduates.
Tuesday, September 25, 2018 2:00PM-2:50PM Stratton Hall 106