Online Algorithms for Edge Coloring

In this thesis, we study online algorithms for edge coloring in various settings, and settle a long-standing conjecture regarding this problem. An edge coloring of a (standard, undirected) graph $G$ is an assignment of colors to the edges of $G$, such that no vertex is incident to two edges of the same color. If the graph $G$ is known, by Vizing's theorem one needs either $\Delta$ or $\Delta + 1$ colors to color $G$ optimally, i.e., using a minimal amount of colors, where $\Delta$ is the maximum degree in $G$. However, if the graph $G$ is given \emph{online}, that is edge by edge or vertex by vertex, with the algorithm having to color all arriving edge(s) before getting to see the next part of the input, it is in general open how many colors are needed. In particular, in the paper which introduced this problem, Bar-Noy et al. \cite{bar1992greedy} conjectured that it should be possible to obtain an asymptotically optimal result under some mild (and necessary) technical constraints. Concretely, they believed that $(1+o(1))\Delta$ randomized edge-coloring algorithms should exist as soon as $\Delta$ is assumed to be known by the algorithm, and $\Delta = \omega(\log n)$.

Our aim is to understand not only whether this conjecture holds, but also where the limit lies between "good'' settings in which close-to-optimal online algorithms edge coloring provably exist, and "bad'' settings in which such algorithms provably do not exist.

In the first part of the thesis, we settle the conjecture of Bar-Noy et al. by proving that, even if $G$ is given edge by edge, this being the most general arrival model, one can $(1+o(1))\Delta$-edge-color the graph by using a randomized algorithm. To prove this result, we design a new algorithm and introduce a technical novelty for analyzing it, which consists of a different way of analyzing correlations between certain random events. Previous work has mostly focused on a direct approach, arguing that the relevant correlations are negative, which allows the use of Chernoff-like inequalities to prove high probability statements. Our approach analyzes the correlations implicitly, by instead reducing to a martingale-based analysis and using martingale-specific concentration inequalities, such as Azuma-Hoeffding and Freedman.

In the second part of the thesis, we prove two stronger results than what Bar-Noy et al. originally envisioned. First, we show that the previous result can be obtained even by a deterministic algorithm (again, assuming $\Delta = \omega(\log n)$), showing that -- somewhat surprisingly -- randomization is not necessary for this problem. Second, we give a randomized algorithm that can achieve an asymptotically optimal coloring even under the weakened hypothesis that $\Delta = \omega(\sqrt{\log n})$. Both of these thresholds, $\Delta = \omega(\log n)$ for deterministic algorithms, and $\Delta = \omega(\sqrt{\log n})$ for randomized algorithms, are known to be optimal already since Bar-Noy et al. published t