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

Area of Science:

• Computer Science
• Artificial Intelligence
• Operations Research

Background:

• The graph coloring problem (GCP) is a critical NP-hard combinatorial optimization problem with wide-ranging applications.
• Existing exact and heuristic methods struggle with large or dynamic graphs, necessitating advanced solutions.
• Recent advancements in neural networks, particularly Graph Neural Networks (GNNs), offer promising alternatives for GCP.

Purpose of the Study:

• To systematically review and consolidate recent neural network approaches to the GCP (2019-2025).
• To identify common architectures, benchmark datasets, and evaluation strategies for neural network-based GCP solutions.
• To highlight persistent challenges and outline future research directions in this domain.

Main Methods:

• A comprehensive literature review of neural network applications to the GCP.
• Categorization of methods into supervised, unsupervised, and reinforcement learning approaches.
• Analysis of benchmark datasets (e.g., COLOR, DIMACS) and their role in evaluating performance.

Main Results:

• Identification of prevalent neural network architectures and common approaches for tackling the GCP.
• Assessment of the effectiveness of various methods on standard benchmark datasets.
• Highlighting key challenges including computational expense, interpretability, and dataset limitations.

Conclusions:

• Neural networks, especially GNNs, show significant potential for solving the GCP.
• Further research is needed to improve generalization, reduce computational costs, and enhance interpretability.
• Developing new benchmarks and real-world applications is crucial for advancing the field.