11
$\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$
2
  • $\begingroup$ For what it's worth, in proposition 6.5 of my unpublished note “The Hadwiger-Nelson problem over certain fields” I prove that $\chi(G')\geq 3$ (which is easy, and probably not original). $\endgroup$
    – Gro-Tsen
    Aug 29, 2023 at 12:49
  • $\begingroup$ "It is relatively easy to see that the chromatic number is one of the number $4,5,6,7$...." As readers probably know, in 2018, Aubrey de Grey ruled out $4$, arxiv.org/abs/1804.02385 $\endgroup$ Aug 29, 2023 at 23:48

1 Answer 1

7
$\begingroup$

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

Olga Kosheleva & Vladik Kreinovich, “On chromatic numbers of space-times: open problems” (UTEP Technical Report UTEP-CS-08-42)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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