The Hadwiger–Nelson problem asks for the minimum number of colors required to color the plane such that no two points at distance 1 from each other have the same color.

We could build the following discrete variant on the infinite two dimensional integer grid (the nodes are points with integer coordinates).

[Discrete Hadwiger–Nelson problem variant] Given an integer $U$ (which is the equivalent of the unit distance in the Hadwiger–Nelson problem), and an integer tolerance distance $t < U$; we consider the infinite induced subgraph $G_{U,t}$ of the integer grid in which two integer points $(x_1,y_1), (x_2, y_2)$ are linked if their distance $d$ is in the interval $[U-t, U+t]$ ( $$|U - ((x_1 - x_2)^2 + (y_1 - y_2)^2)^{1/2}| <= t$$ What is the chromatic number of $G_{U,t}$ ?

Is this problem known?
If it is known, can you give some references?


This problem is equivalent to coloring all points of the plane such that no two points at distance $1\pm\varepsilon$ have the same color (if $t$ is small enough compared to $U$). This has been posed here by Benoît Kloeckner and shown by me that we need at least $6$ colors. For completeness, the argument for your variant.

Color every point of the plane to the color of the integer point nearest to it. This new coloring avoids distance $U$ if $t\ge \sqrt 2/2$, and every color class is a nice region, for which it is known that we need at least 6 colors, see Townsend, Woodall.

Accidentally, just when searching for the links to the papers, I've discovered that Benoît's problem has been studied before a lot, see this paper for a nice historical summary.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.