meditationatae

Just another WordPress.com site

Graph coloring program report 1 vertex conflict

Previously, I thought there could be zero conflicts, two or more conflicts, but not exactly one vertex conflict; I’m not sure what’s going on.

For 500-vertex graph DSJC500.5.col , program reports 1 vertex conflict (??):

 

Added July 31: It’s one edge conflict, or two vertices connected by an edge, and who share the same color.

I’m testing a new version of my  program now.

=====

Added August 4:

Producing a valid 48-coloring of the 500-vertex graph DSJC500.5.col  is much easier than producing a valid 47-coloring.

For 47-colorings, I’ve managed to produce improper 47-colorings with just two problem vertices, i.e. two vertices connected by an edge and that share the same color.

Getting it down from two vertices with conflicts to zero has proved elusive, and seems quite a bit harder.

=====

 

 

54 87 62 23
num_generation = 1069
num_conflicts = 1

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

Advertisements

Written by meditationatae

July 30, 2017 at 2:48 pm

Posted in History

%d bloggers like this: