The Greedy Algorithm is Not Optimal for On-line Edge Coloring
January 16, 2019 (GHC 8102)

The classic edge coloring problem asks to partition the edges of a graph into as few matchings (colors) as possible. By Vizing's theorem, any graph of maximum degree Delta can be edge colored using Delta+1 colors (in polynomial time). However, in many applications of edge coloring the graph is not entirely known in advance, making the problem harder. Motivated by such applications, we study edge coloring in the online adversarial vertex arrival model of Karp, Vazirani and Vazirani. Under such adversarial arrivals, a 1992 paper of Bar-Noy, Naor and Motwani, titled simply ‘’The greedy algorithm is optimal for on-line edge coloring’’, proves the optimality of the trivial greedy algorithm, which on graphs with maximum degree Delta requires 2Delta-1 colors. However, their online lower bound requires Delta=O(log n), and they conjectured the existence of better algorithms than greedy for Delta large enough. We resolve this conjecture positively for bipartite graphs with Delta=omega(logn), and present optimal algorithms (up to o(1) terms) for such graphs. Moreover, we show a surprising dichotomy between the setting where Delta is known apriori and when this crucial parameter is unknown, and present optimal bounds for both known and unknown Delta scenarios.

Joint work with Ilan Reuven Cohen and Binghui Peng.