A heuristic for graph coloring based on the ising model

Bihani, Omkar Narayan (avtor), Žerovnik, Janez (avtor)

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.

• Jezik: Angleški jezik
• Ključne besede: randomized algorithm, graph coloring, chromatic number, generalized Boltzmann machine
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FS - Fakulteta za strojništvo
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2025
• Št. strani: 20 str.
• Številčenje: Vol. 13, no. 18, art. 2976
• PID: 20.500.12556/RUL-173447
• UDK: 004.421.2:519.17
• ISSN pri članku: 2227-7390
• DOI: 10.3390/math13182976
• COBISS.SI-ID: 249224707
• Datum objave v RUL: 17.09.2025

Gradivo je del revije

• Naslov: Mathematics
• Skrajšan naslov: Mathematics
• Založnik: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: verjetnostni algoritem, barvanje grafov, kromatično število, posplošen Boltzmannov stroj