First-Fit Coloring of Forests in Random Arrival Model
<|reference_start|>First-Fit Coloring of Forests in Random Arrival Model: 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.<|reference_end|>
@article{bosek2024first-fit,
    title={First-Fit Coloring of Forests in Random Arrival Model},
    author={Bart{l}omiej Bosek, Grzegorz Gutowski, Micha{l} Laso'n, Jakub
  Przyby{l}o},
    journal={arXiv preprint arXiv:2404.17011},
    year={2024},
    doi={10.4230/LIPIcs.MFCS.2024.33},
    archivePrefix={arXiv},
    eprint={2404.17011},
    primaryClass={cs.DM}
}