Unit Distance Graphs
Consider the plane as a
metric space with a distance function derived from a vector-norm. A unit
distance graph is then a set of points (the vertices) in the plane together
with a set of lines (the edges), each line connecting two vertices whose
distance is equal to 1. We try to colour the
vertices such that two neighbours (i.e. two vertices connected by en edge)
always receive different colours. The necessary number of
colours depends on the metric. In the papers I have now
removed, I was mainly interested in an accurate description of the
quadrangular and hexagonal cases. In the remaining paper I
show that certain graphs (for instance K_5) cannot be induced subgraphs of a
unit distance graph in a polygonal geometry. Papers: |