Vertex Coloring

Here is a list of Graph-Vertex Coloring instances used in the literature. For each instance the table gives:

For each instance we report:

• • |V| number of vertices

  • |E| number of edges

  • d% graph density, corresponding to the number of edges divided by (|V| choose 2)

  • w_LB(G) lower bound to the size of the maximum clique  

  • w_(G) the size of the maximum clique

  • theta(G)  the theta number computed via semidefinite programming

  • X_f(G)  the fractional chromatic number

  • X_LB(G)  lower bound to the chromatic number if computed in a way different from the previous  

  • X(G)   chromatic number

  • X_UB(G)  upper bound to the chromatic number, aka heuristic solution

References are by means of the same keys used in the Bibliography.

Classification

The instances are classified according to their difficulty. We follow the SteinLib classification:

All instances for which no polynomial time algorithm is known are classified as NP.

The letter after this identifier indicates how long it takes to solve the problem using state-of-the-art soft- and hardware.

• • seconds means less than a minute (this includes instances which can be solved in fractions of a second)

  • minutes means less than an hour

  • hours is less than a day

  • days is less than a week

  • weeks means it takes really a long time to solve this instance

  • ? means the instance is not solved or the time is not known. If the chromatic number is given for this instances, then it is known by construction.

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, 8, 424-436 ] 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), and then let us know, by sending us both the upper bound and its "certificate".