Solving Graph Coloring Problem via Graph Neural Network (GNN)

The Graph Coloring Problem (GCP) is concerned with finding the chromatic number, i.e., the minimum number of unique colors required to color adjacent nodes in the graph. Given that combinatorial problems such as GCP are computationally expensive, heuristic-based algorithms are generally employed., and they do not provide optimum solutions. In this work, we utilized Graph Neural networks (GNNs) for finding solution to graph coloring problem, and evaluated our approach against two other contemporary algorithms. Our results demonstrate that our approach can be used to ascertain the chromatic number of a large graph with higher accuracy than the contemporary methods.