A notorious problem in combinatorics is the following:
If we color $\mathbb{R}^2$ so that no pair of points at unit distance get the same color, what is the fewest number of colors required?
This number is sometimes called "the chromatic number of the plane" $\chi$ (since it is really a graph coloring problem on an infinite graph), and it is easily see that $ 4 \le \chi \le 7$ but these bounds have stood for quite a while.
It is natural to ask about coloring other metric spaces, and many people have. In particular, there are bounds known for the chromatic number of $\mathbb{R}^d$ for $d \ge 3$ (and some asymptotics as $d \to \infty$). Also there has been some work on coloring the two-dimensional sphere of radius $r$. (A nice reference for this kind of problem is Soifer's "The mathematical coloring book.")
My question is whether anyone has looked at the chromatic number of the hyperbolic plane. As with the sphere, there is a free parameter — one could either take fixed curvature $-1$ and let the distance vary, or fix unit distance and let the constant negative curvature vary.
We might not expect to be able to solve this in general, since determining the chromatic number of the plane seems difficult, and now we have an infinite family of such problems. But we should be able to put bounds, and I am wondering what is known.
In particular, the following two questions come to mind. I would appreciate insights or pointers to references if these things have been previously studied.
(1) Is there a $5$-chromatic unit distance graph in the hyperbolic plane (for some constant negative curvature)?
(2) Is there an absolute upper bound
on the chromatic number of the hyperbolic
plane, that holds for all constant
negative curvatures?
One might guess that the chromatic number of the hyperbolic plane is increasing as the constant negative curvature decreases, but if so does it grow without bound?
Best Answer
This does not really answer your questions, but I recently got a few results on the chromatic number of the hyperbolic planes. They are formulated by fixing the curvature and letting the distance vary, and I use the notation $\chi(\mathbb{H}^2,\{d\})$ for the chromatic number of the distance-$d$ graph on the hyperbolic plane with curvature $-1$.
for small $d$, $\chi(\mathbb{H}^2,\{d\})\leq 12$ (this can probably be improved, but maybe not easily to $7$),
for large $d$, $\chi(\mathbb{H}^2,\{d\})\leq \frac{4}{\ln 3} d + O(1)$.
The proofs can be found here: https://arxiv.org/abs/1305.2765, published in Geombinatorics Vol XXIV (3) 2015, pp. 117-134 (but the proof of the linear upper bound has some small issues, corrected with an improved bound in the subsequent work of Parlier and Petit https://arxiv.org/abs/1701.08648). All this is not difficult, and the paper raises more questions than it answers.
My impression is that the monotony of the chromatic number with $d$ seems reasonable, but is in fact a subtle issue; and I would rather bet on a negative answer to question (2) but not too high. All in all, these questions are probably incredibly difficult, because we have only very cumbersome tools to relate the geometry with the distance graph.
For the story: about one year after I read, liked and bookmarked your question, I had forgotten about it but read "Ramsey Theory, Today, and Tomorrow", and realized I could answer some questions asked in it by Johnson and Szlam. In the course of writing a paper from these answers, I investigated the case of the hyperbolic plane. After writing a first version I happened to look at my MO favorites, and saw your question again -- which is therefore cited in the paper (will there soon be a @mathoverflow in standard bibTeX definitions?)