References are by means of the same keys used in the Bibliography.
For each instance we report:
Here is a list of Graph-Vertex Coloring instances used in the literature. For each instance the table gives:
The instances are classified according to their difficulty. We follow the SteinLib classification:
The letter after this identifier indicates how long it takes to solve the problem using state-of-the-art soft- and hardware.
The solvers used to distinguish the instances are: DSATUR backtracking search, GeCol (available from the Software section) and the branch-and-price algorithm from [GM10]. The classification may change in the future with the introduction of new contributed solvers.
The maximum clique number is computed with Cliquer [Östergård, P. R. J., A new algorithm for
the maximum-weight clique problem Nordic Journal of Computing, 2001,
] while lower bounds to it are determined by the best result returned by Qualex [Busygin, S. A New Trust Region Technique for the
Maximum Weight Clique Problem Discrete Applied Mathematics, 2006,
154, 2080-2096] or Tabu Search
[Battiti, R. & Mascia, F. Reactive and Dynamic
Local Search for Max-Clique: Engineering Effective Building Blocks Computers
& Operations Research, Elsevier, 2010, 37, 534-542].
If you think you have a best upper bound, please, first check that it is indeed a valid solution (you can use the validator http://www.imada.sdu.dk/~marco/gcp/gcp_check_sol/), and then let us know, by sending us both the upper bound and its "certificate".