Coloring and list-coloring graphs on a fixed surface and minor-closed class of graphs
by
Ken-ichi Kawarabayashi
National Institute of Informatics, Japan
Coauthors: Bojan Mohar, Carsten Thomassen and Bruce Reed

An interesting variant of the classical problem of properly coloring the vertices of a graph with the minimum possible number of colors arises when one imposes some restrictions on the colors or the number of colors available to particular vertices. This variant received a considerable amount of attention by many researchers, and that led to several beautiful conjectures and results. This subject, known as list-coloring, was first introduced in the second half of the 1970s, in two papers by Vizing and independently by Erdös, Rubin and Taylor.

In this talk, we are interested in the list chromatic number in bounded genus graphs and minor-closed class of graphs.

We discuss 5-list-colorability of graphs on a fixed surface, and some approximation algorithms for minor-closed class of graphs. We also relate our results to the famous Hadwiger's Conjecture, and its algorithmic aspect. If time permits, we discuss exponentially many list-colorings in minor-closed class of graphs.

Date received: May 5, 2008