20.500.12556/RUL-173447 A heuristic for graph coloring based on the ising model 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. randomized algorithm graph coloring chromatic number generalized Boltzmann machine verjetnostni algoritem barvanje grafov kromatično število posplošen Boltzmannov stroj true false true Angleški jezik Slovenski jezik Članek v reviji 2025-09-17 09:48:00 2025-09-17 09:48:06 2025-09-18 04:35:32 0000-00-00 00:00:00 2025 0 0 20 str. no. 18, art. 2976 Vol. 13 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.421.2:519.17 2227-7390 10.3390/math13182976 249224707 Bihani,_Zerovnik_..._A_heuristic....pdf Bihani,_Zerovnik_..._A_heuristic....pdf 1 E1E247C4543E3FE77D4DA82BFA352B9D 5bcc9360a480bac28dfa53cf9a3a9d69e2128a0c1ab2a2f7e315f5efaeac86a2 c493ac4f-939a-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=217859 https://www.mdpi.com/2227-7390/13/18/2976 1 7a093f4a-939a-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=217858 Fakulteta za strojništvo 0 0 0