A Systematic Review of Deep Learning and Graph Neural Network Methods for the Graph Coloring Problem: Achievements, Theoretical Gaps, and Future Directions

A Systematic Review of Deep Learning and Graph Neural Network Methods for the Graph Coloring Problem: Achievements, Theoretical Gaps, and Future Directions

Abbas Jafarzadeh1 Morteza Khani Dehnoi2

1) Department of Mathematics, Faculty of Engineering, Quchan University of Technology, Quchan, Iran,
2) Department of Computer Engineering, Faculty of Electrical and Computer Engineering, Quchan University of Technology, Quchan, Iran,

IOI Code : ACCA-ACACHZ
Publication : 4th International Congress on Science, engineering & New Technologies(secongress.com)
Abstract :
    The graph coloring problem (GCP) is one of the most fundamental NP-hard combinatorial optimization problems, with wide-ranging applications in scheduling, register allocation, frequency assignment, and resource management. Traditional heuristic and exact methods exhibit poor scalability when confronted with large or dynamic graphs, which has motivated a turn toward learning-based approaches. This paper presents a systematic literature review (SLR) following the PRISMA protocol of studies published between 2019 and 2025 that investigate the application of neural networks—particularly graph neural networks (GNNs)—to GCP. Following searches in IEEE Xplore, ScienceDirect, SpringerLink, and arXiv and the application of inclusion and exclusion criteria, 18 studies were selected for final analysis; of these, 13 are primary learning-based studies that form the core of the synthesis, while 5 non-neural/heuristic studies are included for comparative context. Findings indicate that learning approaches are organized under three principal paradigms—supervised, unsupervised, and reinforcement learning—and that GNNs, owing to their capacity to encode local graph structure, constitute the shared core of most recent methods. However, critical analysis from the standpoint of graph theory reveals a substantial theoretical gap between empirical heuristic guarantees and precise mathematical bounds on the chromatic number. Most studies lack convergence analysis and theoretical error bounds, and evaluations remain confined to the limited DIMACS and COLOR benchmark suites. This review proposes future research directions emphasizing the need to bridge learning methods with spectral theory and theoretical bounds in graphs.

Keywords : graph coloring problem graph neural network reinforcement learning combinatorial optimization systematic review