Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

A graph G = (V,E) is said to be k-choosable if, given any set of |V| lists of k colors each, one list at each vertex, there is a choice of colors that constitute a proper coloring of the graph. Clearly the choice number of a graph is at least its chromatic number; for general graphs the choice number can be much bigger. A longstanding conjecture, attributed variously to Vizing, Albertson, Collins, Tucker and Gupta, states that the two parameters are in fact equal on the class of line graphs (edge-incidence graphs of graphs).

There is in fact a natural way to translate the question of choosability in a graph to a question about nonzero evaluations of a polynomial associated to it (the product of the linear terms x_i - x_j, over all edges ij of the graph). In this talk, we survey a polynomial approach to choosability via the Alon-Tarsi Combinatorial Nullstellensatz. We give a generalized view of this technique using Groebner bases following work of De Loera, and we give a new proof of a result of Goddyn and Ellingham stating that planar, d-regular, d-edge-colorable graphs satisfy the aforementioned List Coloring Conjecture.