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