Online Edge Coloring with Tree Recurrences

Janani Sundaresan

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.

Date
Feb 9, 2024 12:00 PM
Location
MC6029