Brahadeesh Sankarnarayanan

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.
Date
Wed, June 9, 2021
Start Time
3:00pm-4:00pm IST
Duration
1 hour
Priority
5-Medium
Access
Public
Created by
DEFAULT ADMINISTRATOR
Updated
Sat, June 5, 2021 9:22pm IST