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:

• 1. GEOM: geometric instances

  2. MISC: miscellaneous instances considered standard benchmarks [http://mat.gsia.cmu.edu/COLOR04/]

  3. 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

[GM10] http://www.optimization-online.org/DB_HTML/2010/03/2568.html.