  Given a metric space and a set of distances, one constructs the associated
distance graph by taking as vertices the points of the space and as edges the
pairs whose distance is in the given set. It is a longstanding open question to
determine the chromatic number of the graph obtained from the Euclidean plane
and a set reduced to one distance. Surprisingly, while many variants of this
problem have been studied, only a few non-Euclidean spaces seem to have been
seriously considered. In this paper, we consider the planar
translation-invariant metrics and the hyperbolic plane. We answer questions of
Johnson and Szlam, prove a few other results, and ask many questions.

Combinatorics