graph-theory – Computer Search for a 5-Chromatic Unit Distance Graph

graph theorygraph-colorings

The existence of a 4-chromatic unit distance graph (e.g., the Moser spindle) establishes a lower bound of 4 for the chromatic number of the plane (see the Nelson-Hadwiger problem).

Obviously, it would be nice to have an example of a 5-chromatic unit distance graph. To the best of my knowledge, the existence of such a graph is open. Has there been any (documented) attempt to find such a graph through a computer search? For instance, has every $n$-vertex possibility been checked up to some $n$?

Best Answer

As of this morning there is a paper on the ArXiv claiming to show that there exists a 5-chromatic unit distance graph with $1567$ vertices. The paper is written by non-mathematician Aubrey De Grey (of anti-aging fame), but it appears to be a serious paper. Time will tell if it holds up to scrutiny.

EDIT: in fact, it must be the one with 1585 vertices, according to checkers, see https://dustingmixon.wordpress.com/2018/04/10/the-chromatic-number-of-the-plane-is-at-least-5/

Related Question