What is the graph coloring problem that Paul Erdős offered $25 to solve circa 1979?

125 Views Asked by At

I know that what I am asking is not a mathematics question, but a question about a mathematics question, so if it is inappropriate and you're thinking to downvote, I would appreciate a comment first, so that I can delete it or change it (I don't have a lot of reputation here).

I heard something about a \$25 prize offered by Paul Erdős for determining the number of colors required for coloring graphene, and I wanted to know what the exact question is, because I thought Erdős didn't spend a lot of money (and \$25 back then was about \$100 now). However, the only thing I could find about it was some text in German, and I tried Google translate but the precise description of the problem is not clear:

1979 löste er ein Problem von Paul Erdős über die Färbung von Graphen (von Erdős mit 25 Dollar dotiert). Er benutzte einen Computer, um eine ebene Menge mit 6448 Punkten ohne gleichseitige Dreiecke der Länge 1 zu konstruieren, deren zugehöriger Graph (Punkte wurden jeweils verbunden falls Abstand 1) nicht mit drei Farben färbbar war (chromatische Zahl 4), entgegen der Vermutung von Erdös und zu dessen Überraschung.

I searched so many things such as "graphene chromatic number Erdos" and "graphene graph coloring Erdos" and similar searches but absolutely nothing came up!

1

There are 1 best solutions below

3
On

The apparently refers to a problem inspired by the problem of "coloring the the plane." Let $G_p$ be the graph whose vertices are the points of the plane, and two vertices are adjacent if the difference between them is $1.$ The problem is to compute the chromatic number of $G_p.$

Here is a snippet from the cited source: enter image description here