References & Citations
Computer Science > Discrete Mathematics
Title: First-Fit Coloring of Forests in Random Arrival Model
(Submitted on 25 Apr 2024)
Abstract: 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 $(\frac{1}{2} + 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.
Submission history
From: Grzegorz Gutowski [view email][v1] Thu, 25 Apr 2024 20:13:13 GMT (218kb,D)
Link back to: arXiv, form interface, contact.