by Jan Kristian Haugland
So I am just showcasing a few unit distance graphs (UDGs) that I have come across. They may or may not be original and/or considered
to be interesting. All three have chromatic number 4. The first one is 4-regular on 21 vertices and consists of the regular heptagon and the
two heptagrams, connected by seven equilateral triangles. It is an induced subgraph of the second one which is 6-regular on 63 vertices.
The third one is just the induced subgraph of the vertices of the Moser lattice (based on the vertices of the Moser spindle) with squared
distance 0, ⅓, 1 or
from a given vertex.
It has n = 61 vertices and 228 ≈ 0.9495 n4/3 edges. In comparision, many of thedensest known UDGs with n vertices for n up to 30 (listed here) have very close to n4/3 edges, so perhaps a few more edges is possible?
