Description
Title: Some problems in list-colorings of graphs
Speaker: Brahadeesh Sankarnarayanan
Date: Wednesday, 9th June, 2021.
Time: 1500-1600 hrs IST.
Google Meet link: meet.google.com/uja-zmfy-ozr
Abstract: The choice number, or list-chromatic number, is a generalization
of the chromatic number that was introduced independently by Vizing (1976)
and
Erd{\H o}s--Rubin--Taylor (1979). The choice number is generally much more
difficult to compute as compared to the chromatic number. Even when the
choice number is explicitly known, efficient algorithms for specifying a
proper list-coloring are unknown in most interesting cases.
In this talk, I will discuss some of the known results on computing the
choice number and list-colorings of graphs. I will also describe recent
joint work
with Prof. Niranjan Balachandran on computing the choice number of toroidal
triangulations, as well as providing linear time algorithms for
list-coloring them. This will raise several natural questions about
computing the choice
number of graphs embeddable on surfaces.