Friday, February 9, 2024 12:00 pm
-
1:30 pm
EST (GMT -05:00)
Title: Online Edge Coloring with Tree Recurrences
| Speaker: | Janani Sundaresan |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: We will talk about online edge coloring in the edge arrival model. The vertex set V is known, and each edge arrives one by one, where it has to be colored irrevocably immediately. I will present the results from Kulkarni, Liu, Sah, Sawhney and Tarnawski [STOC 2022] which gives an algorithm that colors the graph with (e/e-1 + o(1))\delta colors.