FirstFit online coloring in the random order model
Data Structures and AlgorithmsDiscrete Mathematics
Summary
The authors build on recent work about how the FirstFit coloring method performs better when vertices of trees arrive in random order instead of worst-case order. They extend this to other similar sparse graphs, like cactus graphs and uniform hypertrees, showing similar improvements. They also find that FirstFit uses very few colors on crown graphs under random order, despite needing many colors in the worst-case order. However, they show that just having many connections (density) doesn't guarantee fewer colors, even for bipartite graphs. Finally, they point out some graph types where random order doesn't help much and suggest open questions for future research.
Authors
Xinyu Ye, Yuechuan Xu, Zixuan Wang, Jiaying Zheng, Yaqiao Li
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 /\log\log 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.