Theory of Computing
-------------------
Title     : Online Graph Edge-Coloring in the Random-Order Arrival Model
Authors   : Bahman Bahmani, Aranyak Mehta, and Rajeev Motwani
Volume    : 8
Number    : 25
Pages     : 567-595
URL       : https://theoryofcomputing.org/articles/v008a025

Abstract
--------

A classic theorem by Vizing asserts that if the maximum degree of a
graph is $\Delta$, then it is possible to color its edges, in
polynomial time, using at most $\Delta+1$ colors. However, this
algorithm is offline, i.e., it assumes the whole graph is known in
advance. A natural question then is how well we can do in the online
setting, where the edges of the graph are revealed one by one, and we
need to color each edge as soon as it is added to the graph. Online
edge coloring has an important application in fast switch scheduling.
A natural model is that edges arrive online, but in a random
permutation. Even in the random permutation model, the best proven
approximation factor for any algorithm is the factor 2 of the simple
greedy algorithm (which holds even in the worst-case online model).
The algorithm of Aggarwal et al. (FOCS'03) provides a 1+o(1) factor
algorithm for the case of very dense multi-graphs, when
$\Delta=\omega(n^{2})$, where $n$ is the number of vertices. In this
paper, we show that for graphs with $\Delta=\omega(\log n)$, it is
possible to color the graph with 
$(1 + \frac{e}{e^2-1}+o(1))\Delta \leq 1.43\Delta$ colors, with high
probability, in the online random-order model. Our algorithm is
inspired by a 1.6-approximate distributed offline algorithm of
Panconesi and Srinivasan (PODC'92), which we extend by reusing failed
colors online.

Further, we show how we can extend the algorithm to reuse colors
multiple times, which reduces the approximation factor below
1.43. We conjecture that the algorithm becomes nearly optimal
(i.e., uses $\Delta + o(\Delta)$ colors) with
$O(\log{(\Delta/\log{n})})$ reuses.  We reduce the question to
proving the non-negativity of a certain recursively defined
sequence, which looks true in computer simulations.  This
non-negativity can be proved explicitly for a small number of
reuses, giving improved algorithms: e.g., the algorithm which reuses
colors 5 times uses $1.26\Delta$ colors.

A preliminary version of this paper appeared in the Proceedings 
of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms 
(SODA 2010).