Online Graph Coloring: Competitive Ratios Separating Randomized and Deterministic AlgorithmsResearch Paper
In online graph coloring the vertices of a graph arrive one at a time, each with its edges to the vertices that arrived earlier, and an algorithm must give every new vertex a color immediately and irrevocably, different from the colors of its neighbours. The problem models resource assignment under uncertainty (register allocation, frequency assignment,…