Graph Coloring research benchmarks

Benchmarks

Dataset NameSOTA methodMetricTrendResultsLast Updated

Icosahedral (test)

PI-GNN

4k* (Icosahedral Test)

Jun 4, 2026

Petersen (test)

PI-GNN

3k* (Petersen Test)

Jun 4, 2026

W_14 (test)

PI-GNN

3k* (Chromatic Number Estimate)

Jun 4, 2026

C_31 (test)

PI-GNN

3Estimated Chromatic Number (k*)

Jun 4, 2026

C_30 (test)

PI-GNN

3k*

Jun 4, 2026

K_{4,8} (test)

PI-GNN

2k* (Chromatic Number Estimate)

Jun 4, 2026

K_10 (test)

PI-GNN

8k* Estimate

Jun 4, 2026

Large 20 cycles

v1abs + GatedGCN

20Completion Count

Jun 4, 2026

Small 40 graphs

v1abs + GatedGCN

40Completion Count

Jun 4, 2026

C_7019 (test)

v1abs + GatedGCN

3.4k*

Jun 4, 2026

C_7000 (test)

v2abs + GPS-SAGE

3.9k* (Chromatic Number Estimate)

Jun 4, 2026

21 target distributions Coloring (test)

LLM Synthesis Agent

86.8Quality Score (LLM)

May 15, 2026