Chromatic Number of the Plane is at least 5

The problem

From the usual Euclidean plane we form the following graph: the points of the plane are the vertices of our graph, and two vertices are connected by an edge if they are exactly unit distance apart. The so-called Hadwiger-Nelson problem is to compute the chromatic number of this graph, i.e., the least amount of colors needed to color the graph such that any two vertices connected by an edge have different colors. This number is called the Chromatic Number of the Plane.

More information can be found on the Wikipedia page (link).

New progress

The problem was formulated over half a century ago, and it was quickly shown that the Chromatic Number of the Plane must be 4, 5, 6 or 7. But since then there was no progress on this problem at all.

Last month, a preprint appeared on the arXiv (link) claiming that the Chromatic Number of the Plane is not 4, i.e., it must be either 5, 6 or 7. It seems that the correctness of the arguments is accepted by now.

In the media

Being a problem which is easy to explain to the general audience and since this is the first progress on it since around 50 years, the result went quickly through the media. An example is the following article in the Quanta Magazine: link.


The proof that the Chromatic Number of the Plane is at least 5 is by providing a subgraph that is not 4-colorable. The subgraph proposed in the arXiv-article has 1581 vertices and checking its non-colorability requires computer assistance.

In order to simplify the arguments, there was a polymath proposal (link). The corresponding wiki-page is here and it seems that they managed already to find a non-4-colorable unit-distance-graph with 610 vertices. Another part of the project is about reducing the amount of computer assistance needed to check to non-4-colorability.