HE3COL

This page shows the best results reported in the following paper:
Jin-Kao Hao and Qinghua Wu. "Improving the extraction and expansion method for large graph coloring". Discrete Applied Mathematics 160(16-17): 2397-2407, 2012.

Table1. Best results obtained by IE²COL in the above paper.

No.	Instances	Previous Best K	K(HE³COL)	Coloring Results
01	DSJC1000.1	20	20	DSJC1000.1
02	DSJC1000.5	83	83	DSJC1000.5
03	DSJC1000.9	222	222	DSJC1000.9
04	flat1000_50_0	50	50	flat1000_50_0
05	flat1000_60_0	60	60	flat1000_60_0
06	flat1000_76_0	82	81	flat1000_76_0
07	r1000.5	234	245	r1000.5
08	r1000.1c	98	98	r1000.1c
09	latin_sqr_10	97	98	latin_sqr_10
10	C2000.5	146	145	C2000.5
11	C2000.5	409	408	C2000.9
12	C4000.5	260	259	C4000.5
13	wap01	42	42	wap01
14	wap02	41	41	wap02
15	wap03	44	44	wap03
16	wap04	43	42	wap04
17	wap05	50	50	wap05
18	wap06	40	40	wap06
19	wap07	42	41	wap07
20	wap08	42	42	wap08

Notes:

1. These instances are available at http://www.info.univ-angers.fr/pub/porumbel/graphs/index.html and http://mat.gsia.cmu.edu/COLOR02 , 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:

c₁ c₂ ... c_n

where c_i (i=1,...,n) is the color of the ith vertex (n is the total number of vertices and c_i={0,1,...,K-1}).