Speaker : Dr. Shaily Verma

Title of the Talk : Algorithmic Advances in Graph Coloring: A Focus on Grundy Coloring

Date, Time and venue : 10th January 2025, 3:00 PM - 4:00 PM, at Seminar Hall, Dept of Mathematics.

Abstract : Graph coloring is a central problem in combinatorial optimization with numerous applications in scheduling, register allocation, and frequency assignment. In this talk, I will center on my research contributions in graph coloring problems, particularly my recent work in parameterized complexity of the partial Grundy coloring problem. The partial Grundy coloring problem aims to color the vertices of a given graph with a maximum number of colors under certain constraints. This problem is difficult to solve in polynomial time for general graphs. In other words, partial Grundy coloring is NP-hard for general graphs. This computational difficulty motivates my research on the parameterized complexity of the problem. Parameterized complexity classifies computational problems based on their inherent difficulty with respect to different problem parameters.

To address these computational challenges, recently, I (with co-authors) studied the parameterized complexity of the partial Grundy coloring problem and showed that the problem is solvable in “polynomial time” with respect to the parameter as the number of colors used. This talk will present a fixed-parameter tractable algorithm for the partial Grundy coloring problem, offering efficient solutions when parameterized by the number of colors. These findings advance our understanding of graph coloring's computational complexity.

About the speaker : Dr. Shaily Verma is a post-doctoral researcher at Hasso Plattner Institute in Germany. Her research in theoretical computer science broadly focuses on graph algorithms. Her research interests include parameterized complexity, exact algorithms, and graph theory. Earlier, she worked as a postdoctoral researcher at the Institute of Mathematical Sciences in Chennai. She obtained her Ph.D. from the Department of Mathematics, IIT Delhi.