FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model

@misc{li2026firstfit,
  title = {{FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model}},
  author = {Yaqiao Li and Xin Li},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.15468},
  eprint = {2610.15468},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.15468},
}

TY  - UNPB
TI  - FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model
AU  - Yaqiao Li
AU  - Xin Li
PY  - 2026
DA  - 2026/10/11
PB  - arXiv
DO  - 10.48550/arxiv.2610.15468
UR  - https://arxiv.org/abs/2610.15468
AB  - FirstFit colors each arriving vertex with the smallest positive integer absent from its previously colored neighborhood. We prove that this rule can require n^Ω(1) many colors on certain bipartite graph of n vertices even when the vertices arrive in a uniformly random order. This refutes the conjecture of Bosek, Gutowski, Lasoń, and Przybyło [BGLP24] that FirstFit uses a polylogarithmic expected number of colors on every bipartite graph in the random order model. We obtain the lower bound by analyzing the FirstFit coloring process on random bipartite graphs, where vertices arrive to either side with equal probability, and with an independent edge density n^−x for some 0 < x < 1. Our result can also be viewed as a qualitative strengthening of Kučera [Kuč91], who showed that, for every ε> 0, there are graphs with chromatic number at most n^ε on which FirstFit uses Ω(n/log n) colors in expectation under a uniformly random order. Our result shows that such poor behavior of FirstFit already occurs for χ(G) = 2.
ER  -