Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

Solving the Graph Coloring Problem via DSatur and PI-GNN

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
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover