The program I wrote to search for 47-colorings of the 500-vertex graph DSJC500.5 has found a solution after 5200 runs. It took over three months.
The algorithm used is from Moalic and Gondran’s 2017 conference paper: “Heuristic rope team : a parallel algorithm for graph coloring”.
The coloring is given by the array below with vertex number and color for vertex number going from 1 to 500:
1 1
2 17
3 17
4 33
5 42
6 16
7 6
8 23
9 37
10 44
11 7
12 15
13 27
14 43
15 14
16 7
17 43
18 19
19 25
20 1
21 32
22 4
23 35
24 29
25 38
26 23
27 38
28 21
29 28
30 2
31 41
32 26
33 29
34 23
35 8
36 9
37 11
38 41
39 30
40 10
41 15
42 14
43 11
44 9
45 47
46 40
47 32
48 14
49 40
50 32
51 46
52 19
53 16
54 2
55 3
56 29
57 1
58 35
59 7
60 18
61 39
62 35
63 1
64 7
65 30
66 39
67 23
68 27
69 19
70 17
71 31
72 5
73 26
74 37
75 13
76 43
77 36
78 17
79 1
80 27
81 34
82 28
83 47
84 22
85 40
86 19
87 13
88 19
89 12
90 2
91 21
92 45
93 33
94 12
95 37
96 41
97 5
98 4
99 9
100 10
101 10
102 8
103 14
104 39
105 32
106 38
107 1
108 39
109 47
110 15
111 8
112 8
113 8
114 46
115 47
116 7
117 16
118 27
119 32
120 35
121 4
122 37
123 43
124 22
125 25
126 36
127 45
128 28
129 36
130 3
131 1
132 28
133 29
134 34
135 3
136 31
137 3
138 38
139 28
140 39
141 47
142 15
143 25
144 16
145 24
146 32
147 23
148 26
149 26
150 12
151 17
152 27
153 9
154 4
155 41
156 34
157 45
158 13
159 21
160 35
161 3
162 7
163 14
164 29
165 43
166 16
167 6
168 32
169 29
170 2
171 27
172 47
173 35
174 16
175 6
176 2
177 44
178 32
179 18
180 41
181 1
182 13
183 1
184 21
185 10
186 37
187 28
188 34
189 15
190 3
191 34
192 4
193 47
194 35
195 34
196 9
197 7
198 5
199 33
200 15
201 8
202 45
203 11
204 4
205 24
206 39
207 20
208 41
209 4
210 38
211 19
212 43
213 6
214 12
215 13
216 31
217 1
218 28
219 10
220 6
221 37
222 26
223 43
224 44
225 11
226 16
227 11
228 23
229 29
230 21
231 24
232 24
233 20
234 9
235 44
236 21
237 2
238 25
239 7
240 14
241 22
242 33
243 37
244 3
245 11
246 12
247 34
248 11
249 37
250 33
251 32
252 23
253 24
254 45
255 46
256 38
257 44
258 6
259 22
260 21
261 16
262 22
263 27
264 46
265 18
266 4
267 16
268 11
269 2
270 2
271 28
272 30
273 47
274 25
275 32
276 9
277 2
278 36
279 36
280 30
281 36
282 18
283 24
284 15
285 26
286 35
287 12
288 6
289 21
290 23
291 34
292 4
293 35
294 20
295 30
296 13
297 21
298 15
299 9
300 5
301 14
302 19
303 40
304 5
305 16
306 37
307 6
308 10
309 30
310 46
311 17
312 20
313 46
314 33
315 33
316 39
317 18
318 46
319 42
320 26
321 44
322 31
323 24
324 15
325 13
326 44
327 5
328 5
329 30
330 20
331 38
332 6
333 5
334 41
335 5
336 27
337 36
338 34
339 42
340 29
341 16
342 38
343 13
344 39
345 15
346 45
347 18
348 30
349 31
350 14
351 2
352 11
353 22
354 13
355 5
356 12
357 12
358 21
359 17
360 4
361 3
362 41
363 30
364 19
365 26
366 20
367 15
368 3
369 10
370 17
371 18
372 7
373 24
374 21
375 25
376 31
377 11
378 28
379 42
380 40
381 25
382 24
383 8
384 33
385 16
386 29
387 2
388 45
389 6
390 38
391 23
392 8
393 6
394 40
395 8
396 41
397 12
398 31
399 11
400 14
401 5
402 1
403 22
404 20
405 17
406 36
407 34
408 4
409 42
410 12
411 10
412 26
413 26
414 18
415 10
416 45
417 25
418 39
419 1
420 13
421 45
422 7
423 9
424 46
425 24
426 10
427 10
428 27
429 21
430 36
431 3
432 46
433 20
434 14
435 18
436 20
437 20
438 7
439 8
440 39
441 22
442 22
443 2
444 4
445 12
446 42
447 29
448 23
449 37
450 5
451 18
452 35
453 37
454 8
455 7
456 3
457 4
458 33
459 3
460 1
461 45
462 2
463 14
464 25
465 13
466 31
467 26
468 47
469 23
470 19
471 11
472 3
473 22
474 28
475 18
476 6
477 8
478 40
479 17
480 42
481 42
482 36
483 17
484 10
485 6
486 40
487 40
488 12
489 42
490 19
491 20
492 22
493 24
494 43
495 38
496 14
497 19
498 15
499 13
500 44
