Multicoloring
Here is a partial list of the Graph Multicoloring instances used in the literature. The results presented are from [GM10]. For each instance the table gives:
|V(G)|: number of vertices
|E(G)|: number of edges (without counting parallel edges)
d%: graph density
|K|: the maximum number of colors required by a vertex
w_m(G): the maximum clique weight (using number of required colors as vertex weights)
LB: best known lower bound
UB: best known upper bound, with verified certificate
OPT: when we know optimality
Classification
The instances are classified as follows:
GEOM: geometric instances
MISC: miscellaneous instances considered standard benchmarks [http://mat.gsia.cmu.edu/COLOR04/]
COG: conflict graphs obtained by the instances of the MIPLIB2003 [http://miplib.zib.de/]
The spreadsheet below shows in green those instances solved to optimality, and in orange the instances having LB < UB.
There are the results for three sets of instances: Miscellaneous from DIMACS (sheet MISC), Geometric (GEOM), and Conflict Graphs (COG).
The COG instances are available here: http://www-dimat.unipv.it/~gualandi/resources/COGs.tar.gz
