meditationatae

Just another WordPress.com site

Update on unit distance graph solver output

After 186 minutes running time, the solver has solved at least 15 12-vertex unit distance graphs requiring 4 colours.

The first 12-vertex unit distance graph found that was 4-colorable but not 3-colourable had 813 4-colourings, up to permutations of the 4 colours.

After 186 minutes, the range in number of 4-colourings for the 12-vertex unit distance graphs that are not 3-colourable is: 441 to 884  :

[david@localhost golomb17]$ cat udgraph12_solverff9741g.txt | grep count_4_colorings | grep no | sort -u
graph is 3-colorable:no. count_4_colorings = 441
graph is 3-colorable:no. count_4_colorings = 532
graph is 3-colorable:no. count_4_colorings = 579
graph is 3-colorable:no. count_4_colorings = 668
graph is 3-colorable:no. count_4_colorings = 682
graph is 3-colorable:no. count_4_colorings = 696
graph is 3-colorable:no. count_4_colorings = 724
graph is 3-colorable:no. count_4_colorings = 730
graph is 3-colorable:no. count_4_colorings = 743
graph is 3-colorable:no. count_4_colorings = 750
graph is 3-colorable:no. count_4_colorings = 780
graph is 3-colorable:no. count_4_colorings = 813
graph is 3-colorable:no. count_4_colorings = 852
graph is 3-colorable:no. count_4_colorings = 870
graph is 3-colorable:no. count_4_colorings = 884

But what is the minimum possible number of 4-colourings among 12-vertex unit distance graphs, up to colour permutation, when looking at the graphs that are not 3-colourable ?

Advertisements

Written by meditationatae

February 15, 2017 at 12:21 am

Posted in History

%d bloggers like this: