Can I read First-Fit Coloring of Forests in Random Arrival Model on EtoBox?

First-Fit Coloring of Forests in Random Arrival Model by Bosek, Bartłomiej; Gutowski, Grzegorz; Lasoń, Michał; Przybyło, Jakub is a scholarly article available to read on EtoBox.

What is First-Fit Coloring of Forests in Random Arrival Model about?

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 uses, in expectation, at most $(1 + o(1))\cdot \ln n \,/\, \ln\ln n$ different colors to color any forest with $n$ vertices. We also construct a family of forests that shows that this bound is best possible.

Author

Bosek, Bartłomiej; Gutowski, Grzegorz; Lasoń, Michał; Przybyło, Jakub

Published

2024

Language

EN