SOTA Graph Coloring benchmarks and papers with code

Benchmarks

Dataset Name	SOTA Method	Metric
Random Graph Coloring		Node Expansions8	20	4mo ago
Graph Coloring 10 Colors, n=200	BloGDiT	Success Rate18.58	8	2mo ago
Graph Coloring 10 Colors, n=100	BloGDiT	Success Rate53.92	8	2mo ago
Graph Coloring 5 Colors, n=100		Success Rate57.16	8	2mo ago
Graph Coloring 5 Colors n=50		Solved Instances Rate83.08	8	2mo ago
Graph Coloring 10-vertex	GRAM	Conflict3.3	8	2mo ago
Graph Coloring 8-vertex	MDLM	Conflict2.7	8	2mo ago
Graph Coloring G4	NSAM(ours)	Final Reward1	7	4mo ago
Graph Coloring G3	NSAM(ours)	Final Reward1	7	4mo ago
Graph Coloring G2	NSAM(ours)	Final Reward1	7	4mo ago
Graph Coloring G1	NSAM(ours)	Final Reward1	7	4mo ago
Complete (100 sampled tasks)	CCEM	Average Violations0	6	2mo ago
Paley 100 sampled tasks	CCEM	Average Violations1.8	6	2mo ago
Regular Expander 100 sampled tasks	CCEM	Average Violations4.2	6	2mo ago
Holme Kim 2 (100 sampled tasks)	CCEM	Average Violations14	6	2mo ago
Holme Kim 100 sampled tasks	CCEM	Average Violations5	6	2mo ago
Erdos Renyi 2 (100 sampled tasks)	CCEM	Average Violations4.6	6	2mo ago
Erdos Renyi 100 sampled tasks	CCEM	Average Violations2.2	6	2mo ago
Regular Expander 2 (100 sampled tasks)	EBM	Average Violations37.2	5	2mo ago
Graph-Coloring-10 OOD n=200	ConsFormer-LNS	Instance Solved Rate18.4	5	4mo ago
Graph-Coloring-10 n=100 (test)	ConsFormer-LNS	Instance Solved Percentage53.9	5	4mo ago
Graph-Coloring-5 n=100 (OOD)		Instance Solved (%)57.16	5	4mo ago
Graph-Coloring-5 n=50 (test)		Instance Solved Rate83.08	5	4mo ago
Mycielski(C5)^3 (test)	PI-GNN	k* (Chromatic Number Estimate)4	4	1mo ago
KG(9,3) (test)	v1abs + GatedGCN	k*9.5	4	1mo ago

Showing 25 of 37 rows