A New Metaheuristic Algorithm for Large Graph Coloring Problems

Abstract

The Graph Coloring Problem (GCP) is an NP-hard combinatorial optimization problem that involves assigning colors to the vertices of a graph such that no two adjacent vertices share the same color. Due to its computational complexity, exact algorithms are often impractical for solving large-scale instances within reasonable time constraints. Consequently, soft computing techniques—particularly metaheuristics—have been widely employed and demonstrated high efficiency in addressing large GCP instances. In this study, we propose a novel island-based parallel metaheuristic algorithm, referred to as PEM-Color,designed to tackle large instances of the GCP. Ensemble learning, a recent paradigm in machine learning, enhances model performance by aggregating the outputs of multiple distinct models rather than relying on a single one. Building on this idea, PEM-Color integrates three state-of-the-art metaheuristic algorithms—Harris Hawk Optimization, Artificial Bee Colony, and Teaching–Learning-Based Optimization—within a parallel ensemble framework using the Message Passing Interface for efficient distributed computation. To the best of our knowledge, this is the first study to employ an ensemble-based approach that combines multiple metaheuristics for solving the GCP in a parallel computing environment. Extensive experiments were conducted on large-scale graph instances from the well-known DIMACS benchmark set, utilizing 64 processors. The results demonstrate substantial reductions in execution time, with near-linear scalability and speed-up. Moreover, the proposed algorithm achieved superior solution quality, outperforming 13 state-of-the-art algorithms, highlighting its effectiveness and potential for further research in large-scale GCPs.   Received: 30 November 2025 | Revised: 13 May 2026 | Accepted: 23 June 2026   Conflicts of Interest The authors declare that they have no conflicts of interest to this work.   Data Availability Statement Data are available from the corresponding author upon reasonable request.   Author Contribution Statement Tansel Dokeroglu: Conceptualization, Methodology, Software, Formal analysis, Investigation, Resources, Writing – original draft, Writing – review & editing, Supervision, Project administration. Deniz Canturk: Conceptualization, Methodology, Software, Validation, Investigation, Resources, Data curation, Writing – original draft, Visualization, Supervision, Project administration.