{"id":"arxiv/2608.29603","url":"https://arxiv.org/abs/2608.29603","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"FirstFit online coloring in the random order model","domain":"cs.DS","source":"arxiv","authors":["Xinyu Ye","Yuechuan Xu","Zixuan Wang","Jiaying Zheng","Yaqiao Li"],"reviews":0,"subject":"cs.DS","summary":"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)$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-30","reactions":{}}