Tutte Colloquium - David Wajc

Friday, December 15, 2023 3:30 pm - 3:30 pm EST (GMT -05:00)

Title: Online edge colouring

Speaker: David Wajc
Affiliation: Technion — Israel Institute of Technology
Location: MC 5501

Abstract: Vizing's Theorem provides an algorithm that edge colors any graph of maximum degree Δ can be edge-colored using Δ+1 colors, which is necessary for some graphs, and at most one higher than necessary for any graph. In online settings, the trivial greedy algorithm requires 2Δ-1 colors, and Bar-Noy, Motwani and Naor in the early 90s showed that this is best possible, at least in the low-degree regime. In contrast, they conjectured that for graphs of superlogarithmic-in-n maximum degree, much better can be done, and that even (1+o(1))Δ-edge-colorings can be computed online. In this talk I will outline the history of this conjecture, and its recent resolution, together with extensions of a flavor resembling classic and recent results on *list* edge-coloring and "local" edge-coloring.

Talk based in part on joint works with many wonderful collaborators, including Sayan Bhattacharya, Joakim Blikstad, Ilan R. Cohen, Fabrizio Grandoni, Binghui Peng, Amin Saberi, Ola Svensson and Radu Vintan.