meditationatae

Just another WordPress.com site

A 12-vertex, 26-edge, probable unit distance graph

okmarch4scan

The 12-vertex, 26-edge graph shown above is not 3-colorable, and is 4-colorable in 178 ways, up to permutation of the four colors. Numerical evidence suggests that it is a unit distance graph, i.e. embeddable in the plane with all edges of unit length.

My unit distance graph solver found no 12-vertex, non 3-colorable, 4-colorable udg with less than 178 different colorings, counting permutations of the four colors as equivalent. The search was not exahaustive and lasted a day.

Below, I copy the adjacency matrix for the graph above. The rows and columns are not labeled, but it is easy to guess: A for row 1, B for row 2, C for row 3, …. L for row 12; similarly for the labeling of the columns.

I don’t know how to do a fixed-width, or monospace font, in WordPress, so I omit the labels to avoid misalignment.

Adjacency matrix, 12 by 12:

0 1 0 0 0 1 1 1 1 0 0 0
1 0 0 0 0 0 0 0 1 0 1 1
0 0 0 1 0 1 1 0 0 1 0 1
0 0 1 0 1 1 0 0 1 0 0 0
0 0 0 1 0 0 0 1 1 1 1 0
1 0 1 1 0 0 0 1 0 0 0 0
1 0 1 0 0 0 0 0 1 1 0 0
1 0 0 0 1 1 0 0 0 1 1 0
1 1 0 1 1 0 1 0 0 0 0 0
0 0 1 0 1 0 1 1 0 0 0 1
0 1 0 0 1 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0 0 1 0 0

 

Advertisements

Written by meditationatae

March 4, 2017 at 8:28 pm

Posted in History

%d bloggers like this: