## The chromatic number of the Unit Distance Graph

**Problem:**
How many colors are needed so that if each point in the plane
is assigned one of the colors, no two points which are exactly distance 1 apart will
be assigned the same color?

This problem has been open since 1956, the year when I was born. It is known that
at least 4 colors are needed and that 7 colors suffice. Hence, the answer is either 4, 5, 6 or 7.
This is not too hard to show.

A graph which can be represented so that vertices correspond to points in the plane
and edges correspond to unit-length line segments is called a * unit-distance
graph*.
The question above is equivalent to asking what the chromatic number of (finite)
unit-distance graphs can be.
Here are some easier questions, whose answers are known:
Which complete bipartite graphs are unit-distance graphs? What is the smallest 4-chromatic unit-distance graph?
Show that the Petersen graph is a unit-distance graph.

Here is also a seemingly easier **question:**
Is there a positive integer *k* such that every
finite unit-distance graph of girth at least *k* has chromatic number at
most 6 (respectively 5)?

Send comments to Bojan.Mohar@uni-lj.si

##### Revised: september 02, 2001.