|Discrete Mathematics and Optimization Seminar
Monday October 17th at 4.30pm
Title. List-coloring graphs on a fixed surface and minor-closed graphs.
Computing the list-chromatic number seems much harder than
computing the chromatic number. In this talk, we will consider the
following class of graphs.
(1) Graphs closed under taking minors, i.e,
graphs with no K_k minor.
(2) Graphs on a fixed surface.
In (1), we shall give an O(k)-factor approx. algorithm, and
connect this result to the list-coloring version of Hadwiger's conjecture.
In (2), we shall consider 5-list-coloring on a fixed surface and
3-list-coloring with girth at least 5 on a fixed surface.
These results are joint work with B. Mohar and partially, C. Thomassen.