LLM-Generated Heuristics for the Graph Coloring Problem

The graph coloring problem (GCP) is a classic NP-hard combinatorial optimization problem with broad practical applications. This study develops graph coloring heuristics using five frontier large language models (LLMs)—GPT-4o, GPT-5.1, Claude 3.5 Sonnet, DeepSeek-V3, and LLaMA 3.1—to generate vertex-ordering scoring formulas from five graph-theoretic features, with iterative refinement based on failure-instance feedback.

The heuristics are evaluated on 140 synthetic graph instances across three graph families and scales using sequential CPU and parallel CUDA GPU implementations. They are compared against DSATUR, RLF, First-Fit, Jones-Plassmann, Luby’s MIS, and cuGraph, with statistical significance assessed using the Friedman and Nemenyi tests.

LLaMA’s best heuristic, H3, achieves a slightly lower average color count than DSATUR at medium scale, 9.70 versus 9.83, although the difference is not statistically significant and requires roughly 15–21 times more runtime. Four of the five LLMs match DSATUR across all scales, while GPT-5.1 does not. Refinement effects vary by model, with Claude benefiting most consistently. In the parallel setting, all four models producing valid CUDA code outperform Jones-Plassmann and Luby’s MIS in color count and remain statistically comparable to cuGraph, while requiring approximately two to three times its kernel runtime.

Supervisor: Prof. Imtiaz Ahmad

Convener: Prof. Maytham Safar

Examination Committee Member: Prof.Ayed Salman