SOTA Graph Coloring benchmarks and papers with code

Benchmarks

Dataset Name	SOTA Method	Metric
Random Graph Coloring		Node Expansions8	20	3mo ago
Graph Coloring 10 Colors, n=200	BloGDiT	Success Rate18.58	8	8d ago
Graph Coloring 10 Colors, n=100	BloGDiT	Success Rate53.92	8	8d ago
Graph Coloring 5 Colors, n=100		Success Rate57.16	8	8d ago
Graph Coloring 5 Colors n=50		Solved Instances Rate83.08	8	8d ago
Graph Coloring 10-vertex	GRAM	Conflict3.3	8	14d ago
Graph Coloring 8-vertex	MDLM	Conflict2.7	8	14d ago
Graph Coloring G4	NSAM(ours)	Final Reward1	7	3mo ago
Graph Coloring G3	NSAM(ours)	Final Reward1	7	3mo ago
Graph Coloring G2	NSAM(ours)	Final Reward1	7	3mo ago
Graph Coloring G1	NSAM(ours)	Final Reward1	7	3mo ago
Complete (100 sampled tasks)	CCEM	Average Violations0	6	9d ago
Paley 100 sampled tasks	CCEM	Average Violations1.8	6	9d ago
Regular Expander 100 sampled tasks	CCEM	Average Violations4.2	6	9d ago
Holme Kim 2 (100 sampled tasks)	CCEM	Average Violations14	6	9d ago
Holme Kim 100 sampled tasks	CCEM	Average Violations5	6	9d ago
Erdos Renyi 2 (100 sampled tasks)	CCEM	Average Violations4.6	6	9d ago
Erdos Renyi 100 sampled tasks	CCEM	Average Violations2.2	6	9d ago
Regular Expander 2 (100 sampled tasks)	EBM	Average Violations37.2	5	9d ago
Graph-Coloring-10 OOD n=200	ConsFormer-LNS	Instance Solved Rate18.4	5	2mo ago
Graph-Coloring-10 n=100 (test)	ConsFormer-LNS	Instance Solved Percentage53.9	5	2mo ago
Graph-Coloring-5 n=100 (OOD)		Instance Solved (%)57.16	5	2mo ago
Graph-Coloring-5 n=50 (test)		Instance Solved Rate83.08	5	2mo ago
21 target distributions Coloring (test)	LLM Synthesis Agent	Quality Score (LLM)86.8	1	19d ago

Showing 24 of 24 rows