# A deep learning guided memetic framework for graph coloring problems

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 58 references that are in the map.
- First posted on arXiv 13 Sep 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Deep Set Prediction Networks](https://mlsanity.com/paper/1906.06565/) (2019)
- [Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problems](https://mlsanity.com/paper/1903.04598/) (2019)
- [Coloring Big Graphs with AlphaGoZero](https://mlsanity.com/paper/1902.10162/) (2019)
- [Mixed batches and symmetric discriminators for GAN training](https://mlsanity.com/paper/1806.07185/) (2018)
- [Reinforcement learning based local search for grouping problems: A case study on graph coloring](https://mlsanity.com/paper/1604.00377/) (2016)
- [Variations on Memetic Algorithms for Graph Coloring Problems](https://mlsanity.com/paper/1401.2184/) (2014)
- [A memetic algorithm for the minimum sum coloring problem](https://mlsanity.com/paper/1304.2641/) (2013)

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

- [On Monte Carlo Tree Search for Weighted Vertex Coloring](https://mlsanity.com/paper/2202.01665/) (2022)
- [HyColor: An Efficient Heuristic Algorithm for Graph Coloring](https://mlsanity.com/paper/2506.07373/) (2025)
- [Combining Monte Carlo Tree Search and Heuristic Search for Weighted Vertex Coloring](https://mlsanity.com/paper/2304.12146/) (2023)

## Abstract (arXiv)

Given an undirected graph G=(V,E) with a set of vertices V and a set of edges E, a graph coloring problem involves finding a partition of the vertices into different independent sets. In this paper we present a new framework that combines a deep neural network with the best tools of classical metaheuristics for graph coloring. The proposed method is evaluated on two popular graph coloring problems (vertex coloring and weighted coloring). Computational experiments on well-known benchmark graphs show that the proposed approach is able to obtain highly competitive results for both problems. A study of the contribution of deep learning in the method highlights that it is possible to learn relevant patterns useful to obtain better solutions to graph coloring problems.