Contemporary Methods for Graph Coloring as an Example of Discrete Optimization

This paper provides an insight into graph coloring application of the contemporary heuristic methods. It discusses a variety of algorithmic solutions for The Graph Coloring Problem (GCP) and makes recommendations for implementation. The GCP is the NP-hard problem, which aims at finding the minimum number of colors for vertices in such a way, that none of two adjacent vertices are marked with the same color.With the advent of multicore processing technology, the metaheuristic approach to solving GCP reemerged as means of discrete optimization. To explain the phenomenon of these methods, the author makes a thorough survey of AI-based algorithms for GCP, while pointing out the main differences between all these techniques.

---

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).