Advancements in Online Edge Coloring Algorithms

In this presentation, we explore recent advancements in online edge coloring, focusing on new algorithms that achieve near-optimal guarantees by leveraging martingale concentration arguments. Our focus will be on two main results that establish sharp thresholds matching long-standing lower bounds, answering and pushing beyond the original conjecture by Bar-Noy, Motwani, and Naor (BNMN, 1992). 

Firstly, while the BNMN conjecture posited that randomization was necessary to achieve (1+o(1))Delta-coloring for Delta=omega(log n), we present a deterministic online algorithm that achieves this guarantee in the same regime. This result matches the known impossibility result for deterministic algorithms when Delta=O(log n), establishing a sharp threshold. 

Secondly, improving the conditions under which near-optimal coloring is known to be possible randomly, we present a randomized online algorithm achieving a (1+o(1))Delta-edge-coloring already for graphs with maximum degree Delta=omega(sqrt{log n}). This establishes a sharp threshold for randomized algorithms, matching the BNMN lower bound for the Delta=O(sqrt{log n}) regime. 

This is joint work with Joakim Blikstad, Ola Svensson, Radu Vintan, and David Wajc.