# 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
{"ft_lang_label":"__label__en","ft_lang_prob":0.8796496,"math_prob":0.99956816,"size":950,"snap":"2021-04-2021-17","text_gpt3_token_len":318,"char_repetition_ratio":0.10042283,"word_repetition_ratio":0.025974026,"special_character_ratio":0.35578948,"punctuation_ratio":0.11057692,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999579,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-04-18T01:41:35Z\",\"WARC-Record-ID\":\"<urn:uuid:bbcd6510-bd7e-4d2b-83ac-f993cfec4bc2>\",\"Content-Length\":\"130025\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:94d22d4b-26fa-49e8-a0eb-94da2f69f121>\",\"WARC-Concurrent-To\":\"<urn:uuid:2f3ac916-6cbf-43f4-8463-b31c33d5ce9d>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://mathoverflow.net/questions/201790/a-variant-of-nelson-hadwiger-problem-on-the-chromatic-number-of-the-plane\",\"WARC-Payload-Digest\":\"sha1:GIFKFHUON3ZUUKRVFY3RO3TBPVLHAZZE\",\"WARC-Block-Digest\":\"sha1:GJ4K4OJ5HQVWVZKP3GHASMSKPLXLJ5SR\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-17/CC-MAIN-2021-17_segments_1618038464146.56_warc_CC-MAIN-20210418013444-20210418043444-00121.warc.gz\"}"}