9
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

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

$\endgroup$

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.