DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu

Lara Pudwell, Rutgers University, lpudwell {at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: On What We Don't Know (About List Coloring and Related Topics)

Speaker: Paul Raff, Rutgers University

Date: Thursday, January 24, 2008 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Motivated by the quote I heard from Manuel Blum, "Once you prove something, it becomes trivial," I will talk about the frontier of list coloring, which is still wide open. List coloring is a generalization of regular graph coloring where each vertex has its own choice of colors it can be colored with, as opposed to a global list of colors in normal coloring. I will talk mainly about two conjectures, one of Ohba and one of Albertson. Albertson's Conjecture is a list-coloring analogue of a very simple fact of graph coloring, and Ohba's Conjecture tries to identify a large class of graphs where the chromatic number and the list chromatic number are equal. Very litle prior knowledge is required to understand the talk, and many open problems will be discussed.