This page shows the best results reported in the following paper:
Qinghua Wu and Jin-Kao Hao. "Coloring large graphs based on independent set extraction". Computers & Operations Research, Volume 39, Issue 2, Pages 283-290, 2012.
DOI: 10.1016/j.cor.2011.04.002
Table1. Best coloring results on the 11 largest DIMACS graphs obtained by EXTRACOL in the above paper.
| No. | Instances | Previous Best K | K* (EXTRACOL) | Coloring Results |
| 01 | DSJC1000.1 | 20 | 20 | DSJC1000.1 |
| 02 | DSJC1000.5 | 83 | 83 | DSJC1000.5 |
| 03 | DSJC1000.9 | 223 | 222 | DSJC1000.9 |
| 04 | r1000.1c | 98 | 101 | r1000.1c |
| 05 | r1000.5 | 234 | 250 | r1000.5 |
| 06 | flat1000_50_0 | 50 | 50 | flat1000_50_0 |
| 07 | flat1000_60_0 | 60 | 60 | flat1000_60_0 |
| 08 | flat1000_76_0 | 82 | 82 | flat1000_76_0 |
| 09 | C2000.5 | 148 | 146 | C2000.5 |
| 10 | C2000.9 | 413 | 409 | C2000.9 |
| 11 | C4000.5 | 271 | 260 | C4000.5 |
Notes:
1. These instances are available at http://www.info.univ-angers.fr/pub/porumbel/graphs/index.html, or can be provided on request to wu@info.univ-angers.fr or hust2007wu@gmail.com.
2. The format of the solution file is as follows:
K = K*
c1 c2 ... cn
where K* is the number of colors used, while ci (i=1,...,n) is the color of the ith vertex (n is the total number of vertices and ci={0,1,...,K*-1}).