A survey of modern neural network based methods for the graph coloring problem.

Abstract

The graph coloring problem (GCP) is a fundamental NP-hard combinatorial optimization task with applications in scheduling, register allocation, frequency assignment, and resource management. Traditional heuristics and exact methods often scale poorly to large or dynamic graphs, motivating learning-based alternatives. Recent years have seen a surge of interest in applying neural networks to the GCP, yet no systematic survey has consolidated these developments. This review aims to identify the most common approaches and architectures used to apply neural networks to the GCP, summarize the benchmark datasets typically employed to evaluate these methods and assess their effectiveness, and highlight the key challenges that remain in applying neural networks to the GCP. In addressing these objectives, this paper provides a comprehensive review of recent neural network approaches to the GCP in recent years (2019-2025) after the introduction of Graph Neural Networks (GNNs), organizing methods into supervised, unsupervised, and reinforcement learning approaches. The survey highlights progress to date, the role of benchmark datasets, and persistent challenges such as computational cost, interpretability, and reliance on limited benchmarks like COLOR and DIMACS. Finally, we outline future research directions aimed at improving generalization and real-world applicability.