Unit distance graphs
by Jan Kristian Haugland


It is assumed throughout that the graphs are embedded in the Euclidean plane.

(A) I found a couple of nice (?) unit distance graphs (UDGs) based on the regular heptagon. The first one is described in this PDF file.

 

(B) What is the smallest UDG for which the vertices can be assigned non-negative weights such that the weighted independence ratio is less than 2/7,
as attained by the Moser spindle? The following graph on 23 vertices and 60 edges appears to be a strong candidate. If the blue vertex is weighted 3
and the white ones are weighted 1, we obtain the value 7/25. We can remove one red edge and one green edge without affecting this property.



(C) On a related note, if n is a positive integer, what is the smallest UDG with the property that for any 4-colouring, each colour
class contains at least n vertices? For n ≤ 3, I have not found anything better than n copies of the Moser spindle with 7n vertices.
On the other hand, if G is a minimal 5-chromatic UDG, then it provides an answer for n ≥ |V(G)| / 4. It is known that |V(G)| ≤ 509.

For n = 4, 5 and 6, the graphs in the dataset from this paper give an upper bound of 25, 30 and 34 vertices
respectively. I have assumed that the degree of each vertex is at least 4 in order to reduce the search space.

Here are the graphs on 25 vertices for n = 4. The first one has 70 edges, and the others have
69 edges. The two in the middle are isomorphic. Again, some of the edges are redundant.

Coordinates		Coordinates		Coordinates		Coordinates

Each one is an isometric subgraph of the next graph on 33 vertices and 102 edges.

Removing only the green vertices or only the red vertices, or two vertices of the same colour
(green/red) and their common neighbour of degree 6, yields four of the graphs on 30 vertices
for n = 5 (in two isomorphism classes). There are also four others (in three isomorphism classes).


Coordinates

For n = 6, we can remove one of the yellow vertices (and some edges) in the following graph
on 35 vertices and 114 edges, which also happens to be the densest known UDG of that size.
It contains the earlier graph we considered, the one with 23 vertices, as an isometric subgraph.

If we give the red, orange and yellow vertices weight 1 and the green, blue and purple vertices
weight 2, then for any 4-colouring (not to be confused with the colours used in the image in
order to identify the vertices), each colour class has relative size at least 5/26. Here, the two
green-green edges aligned with the purple vertex, and the two blue-blue edges, are redundant.

If we give the orange vertices weight 1, the yellow vertices weight 2, the red and green vertices weight 3,
the purple vertex weight 4 and the blue vertices weight 5, we obtain a weighted independence ratio of 14/51.


Coordinates with colours