Online Edge Coloring: Landscape of Results

A companion to the bachelor's thesis "Online Edge Coloring: A Deterministic Algorithm for Bipartite Multigraphs" (KTH, 2026). Displaying known upper bounds, lower bounds, and open problems across arrival models and graph classes.

$\Delta = \omega($ $)$
$\cap\;O($ $)$
Matches offline optimum
Matches online lower bound
Beats greedy nontrivially
Only greedy $2\Delta{-}1$ known
Click a cell to see details.