A Heuristic for Graph Coloring Based on the Ising Model

Omkar Bihani and Janez Žerovnik ()
Additional contact information
Omkar Bihani: Rudolfovo—Science and Technology Centre Novo mesto, Podbreznik 15, 8000 Novo mesto, Slovenia
Janez Žerovnik: Rudolfovo—Science and Technology Centre Novo mesto, Podbreznik 15, 8000 Novo mesto, Slovenia

Mathematics, 2025, vol. 13, issue 18, 1-20

Abstract: We propose a dynamic extension of the Petford–Welsh coloring algorithm that estimates the chromatic number of a graph without requiring k as an input. The basic algorithm is based on the model that is closely related to the Boltzmann machines that minimize the Ising model Hamiltonian. The method begins with a minimal coloring and adaptively adjusts the number of colors based on solution quality. We evaluate our approach on a variety of graphs from the DIMACS benchmark suite using different initialization strategies. On random k -colorable graphs, proper colorings were found for all combinations of initial strategies and parameter values, while for DIMACS graphs, optimal or near optimal solutions were found frequently, without tuning the parameters. The results show that the algorithm designed is not only capable of providing near optimal solutions but is also very robust. We demonstrate that our approach can be surprisingly effective on real-world instances, although more adaptive or problem-specific strategies may be needed for harder cases. The main advantage of the proposed randomized algorithm is its inherent parallelism that may be explored in future studies.

Keywords: randomized algorithm; graph coloring; chromatic number; generalized Boltzmann machine (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/18/2976/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/18/2976/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:18:p:2976-:d:1749484

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().