The greedy algorithm is optimal for on-line edge coloring (Q1209350)

In this note we are concerned with on-line edge coloring. We show that the greedy algorithm, which has performance ratio 2, is optimal in both the deterministic and the randomized case. In both cases, we define a graph such that any on-line algorithm must use \(2\Delta-1\) colors, independent of whether the graph is given edge-by-edge or vertex-by- vertex. In the deterministic case \(\Delta=O(\log n)\), and in the randomized case \(\Delta=O((\log n)^{1/2})\).