# Online Graph Edge-Coloring in the Random-Order Arrival Model

### Venue

Theory of Computing, vol. 8(1) (2012), pp. 567-595

### Publication Year

2012

### Authors

Bahman Bahmani, Aranyak Mehta, Rajeev Motwani

### BibTeX

## Abstract

A classic theorem by Vizing asserts that if the maximum degree of a graph is ?,
then it is possible to color its edges, in polynomial time, using at most ?+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 ?=?(n2), where n is the number of vertices.
In this paper, we show that for graphs with ?=?(logn), it is possible to color the
graph with (1+ee2?1+o(1))??1.43? 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 ?+o(?) colors)
with O(log(?/logn)) 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?
colors.