Solving the Graph Coloring Problem via DSatur and PI-GNN
Received: 10 Oct 2026 Revised: 22 Oct 2026 Accepted: 07 Nov 2026
Published: 2026, vol. 30, issue 4, pp. 433–436
Abstract
This paper explores a synergistic (hybrid) approach to solving the Graph Coloring Problem (GCP), based on the integration of the classic heuristic DSatur algorithm and the physics-informed graph neural network. The proposed hybrid approach aims to improve coloring accuracy and stability compared to using neural network models in isolation. The results of a comparative analysis of the proposed method against classical algorithms on graphs of various sizes are presented.
Keywords: graph coloring problem, GCP, graph neural networks, GNN, PI-GNN, DSatur.
BibTeX
@article{IS-Filatov2026,
author = {Filatov, D. A.},
title = {{Solving the Graph Coloring Problem via DSatur and PI-GNN}},
journal = {Intelligent Systems. Theory and Applications},
year = {2026},
volume = {30},
number = {4},
pages = {433--436},
}
AMSBIB
\Bibitem{IS-Filatov2026}
\by D.\,A.~Filatov
\paper Solving the Graph Coloring Problem via DSatur and PI-GNN
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 433--436
\lang In Russian
RU