First-Fit Coloring of Forests in Random Arrival Model

Bartłomiej Bosek, Grzegorz Gutowski, Michał Lasoń +1

We consider a graph coloring algorithm that processes vertices in order taken uniformly at random and assigns colors to them using First-Fit strategy. We show that this algorithm u…