In Number Theory, Logic, and Cryptography

Chromatic Number


Suppose you wanted to paint the plane. What is the minimum number of colors you would need so that all pairs of points exactly 1 unit from each other were a different color?

It must be at least four - see the graph on the left (known as the Moser Spindle), where the lines show distances of exactly one unit. At least four colors are needed to ensure that connected nodes are different colors. Recent advances have raised this lower limit to five.












At the same time, it is known that seven colors will suffice: for example the solution on the right, taken from {2}, where the circles shown have radius 1 unit.


The problem is to find a solution to coloring the plane that uses less than 7 colors, or raise the possible lower bound above 5.


For further information, please see:

[1] http://en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem

[2] http://www.mathpuzzle.com/chrompln.html

[3] http://maven.smith.edu/~orourke/TOPP/P57.html



You can check for contributions to this problem on the solutions page.



This web site developed and maintained by

Tim S Roberts

Email: timro21@gmail.com