# Monte Carlo Graph Coloring

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 29 references that are in the map.
- First posted on arXiv 4 Apr 2025.

## Builds on (most cited first, 2 of 2)

- [Variations on Memetic Algorithms for Graph Coloring Problems](https://mlsanity.com/paper/1401.2184/) (2014)
- [Finer Tight Bounds for Coloring on Clique-Width](https://mlsanity.com/paper/1804.07975/) (2018)

## Abstract (arXiv)

Graph Coloring is probably one of the most studied and famous problem in graph algorithms. Exact methods fail to solve instances with more than few hundred vertices, therefore, a large number of heuristics have been proposed. Nested Monte Carlo Search (NMCS) and Nested Rollout Policy Adaptation (NRPA) are Monte Carlo search algorithms for single player games. Surprisingly, few work has been dedicated to evaluating Monte Carlo search algorithms to combinatorial graph problems. In this paper we expose how to efficiently apply Monte Carlo search to Graph Coloring and compare this approach to existing ones.