Discrete Mathematics and Optimization Seminar


Ken-ichi Kawarabayashi
Tohoku University
Monday October 17th at 4.30pm
Burnside 1205



Title. List-coloring graphs on a fixed surface and minor-closed graphs.

Abstract. 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.