# Online Graph Coloring with Predictions

arXiv: https://arxiv.org/abs/2312.00601 · HTML: https://mlsanity.com/paper/2312.00601/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Dec 2023.

## Built on by (most cited first, 5 of 5)

- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency](https://mlsanity.com/paper/2507.16242/) (2025)
- [Online Learning with Sublinear Best-Action Queries](https://mlsanity.com/paper/2407.16355/) (2024)
- [Efficient Approximate Temporal Triangle Counting in Streaming with Predictions](https://mlsanity.com/paper/2506.13173/) (2025)
- [Towards Optimal Robustness in Learning-Augmented Paging](https://mlsanity.com/paper/2606.01342/) (2026)

## Abstract (arXiv)

We introduce learning augmented algorithms to the online graph coloring problem. Although the simple greedy algorithm FirstFit is known to perform poorly in the worst case, we are able to establish a relationship between the structure of any input graph G that is revealed online and the number of colors that FirstFit uses for G. Based on this relationship, we propose an online coloring algorithm FirstFitPredictions that extends FirstFit while making use of machine learned predictions. We show that FirstFitPredictions is both consistent and smooth. Moreover, we develop a novel framework for combining online algorithms at runtime specifically for the online graph coloring problem. Finally, we show how this framework can be used to robustify by combining it with any classical online coloring algorithm (that disregards the predictions).