Here is a list of Graph-Vertex Coloring instances used in the literature. For each instance the table gives: - |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
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. -
**s**econds means less than a minute (this includes instances which can be solved in fractions of a second) -
**m**inutes means less than an hour **h**ours is less than a day**d**ays is less than a week-
**w**eeks 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 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". |