FirstFit online coloring in the random order model
Abstract
The average performance of FirstFit online coloring on trees in the random order model is completely determined in recent works of Frei et al. and Bosek et al., showing Θ(log n /loglog n) number of colors, improving the Θ(log n) colors in the adversarial model. We provide a few further results on slightly more general graph classes. Firstly, we extend their method to obtain a simple path-counting principle for sparse graph classes, which immediately yields for example that cactus graphs and uniform hypertrees exhibit a similar improvement. We then show that FirstFit uses only O(1) colors on crown graphs, a standard example where adversarial arrival forces Θ(n) colors. We further show that density alone (even linear minimum degree) is insufficient to guarantee O(1) colors even on bipartite graphs. Finally, we identify graph classes, including unit interval graphs and some graphs of high chromatic number, for which random arrival provides only limited improvement. We end with some open problems.
Related
- FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model
- Coloring sparse random Cayley graphs
- FIID Coloring Random Maps
- Order 14 is the largest order for which every 4-total coloring of every cubic graph is equitable
- Online Supervised Dimension Reduction with Random Features: Diagnostics and Computational Trade-offs
BibTeX
@misc{ye2026firstfit,
title = {{FirstFit online coloring in the random order model}},
author = {Xinyu Ye and Yuechuan Xu and Zixuan Wang and Jiaying Zheng and Yaqiao Li},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.29603},
eprint = {2608.29603},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.29603},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - FirstFit online coloring in the random order model
AU - Xinyu Ye
AU - Yuechuan Xu
AU - Zixuan Wang
AU - Jiaying Zheng
AU - Yaqiao Li
PY - 2026
DA - 2026/08/30
PB - arXiv
DO - 10.48550/arxiv.2608.29603
UR - https://arxiv.org/abs/2608.29603
AB - The average performance of FirstFit online coloring on trees in the random order model is completely determined in recent works of Frei et al. and Bosek et al., showing Θ(log n /loglog n) number of colors, improving the Θ(log n) colors in the adversarial model. We provide a few further results on slightly more general graph classes. Firstly, we extend their method to obtain a simple path-counting principle for sparse graph classes, which immediately yields for example that cactus graphs and uniform hypertrees exhibit a similar improvement. We then show that FirstFit uses only O(1) colors on crown graphs, a standard example where adversarial arrival forces Θ(n) colors. We further show that density alone (even linear minimum degree) is insufficient to guarantee O(1) colors even on bipartite graphs. Finally, we identify graph classes, including unit interval graphs and some graphs of high chromatic number, for which random arrival provides only limited improvement. We end with some open problems.
ER -