# A variant of Nelson-Hadwiger Problem on the chromatic number of the plane

The famous Nelson-Hadwiger problem asks about the chromatic number of the graph $G$, with the vertex set $V(G)={\mathbb R}^2$ where $a_1=(x_1,y_1), a_2=(x_2,y_2) \in V(G) \$ form an edge iff $a_1-a_2$ has Euclidean length $1$, or equivalently, $$(x_1-x_2)^2+(y_1-y_2)^2=1.$$ It is relatively easy to see that the chromatic number is one of the number $4,5,6,7$, and there is a vast literature on this and some closely related problems.

The question I have come across is the following: consider the graph $G'$ with the same vertex set $V$, but assume that $a_1=(x_1,y_1), a_2=(x_2,y_2) \in V \$ form an edge iff $$(x_1-x_2)^2-(y_1-y_2)^2=1.$$ What is the chromatic number of this graph? Since the set $x^2-y^2=1$ misses a neighborhood of $0$, it is clear that $\chi(G') \le \aleph_0$. But I cannot even show that $\chi( G')$ is finite. I would be thankful if anyone can help by an idea of pointing me to any existing literature on this question.

## 1 Answer

It's apparently an open problem as to whether it's finite:

http://www.cs.utep.edu/vladik/2008/tr08-42.pdf