# Discrete Hadwiger–Nelson problem variant

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?

## 1 Answer

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.