Graph Coloring Algorithm Based on Minimal Cost Graph Neural Network

Abstract

The graph coloring problem functions as a fundamental and pivotal combinatorial optimization task and has played an essential role in various domains such as wireless spectrum management, register planning, and event scheduling. However, traditional coloring algorithms often face limitations such as long computation times and inability to find optimal solutions when dealing with large-scale or complex structured graphs. Against this backdrop, we introduce a graph coloring algorithm underpinned by a Minimal Cost Graph Neural Network (MCGNN). This method incorporates a novel minimum cost optimization mechanism that allows for a deeper exploration of the graph’s structure in comparison to conventional algorithms while leveraging the power of graph neural networks to extract node features for precise graph coloring. Numerical simulations affirm that our scheme not only outperforms existing mainstream methods in finding higher-quality coloring schemes but also does so in reduced computational time.

Keywords

• Graph coloring
• graph neural network (GNN)
• minimal cost graph neural network