Coloring distance graphs: a few answers and many questions

Abstract

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.

17 pp

Cited by in corpus (6)

• Exact distance coloring in trees
• Exact square coloring of subcubic planar graphs
• Chromatic numbers for the hyperbolic plane and discrete analogs
• Lower bounds for the measurable chromatic number of the hyperbolic plane
• On the support of a non-autocorrelated function on a hyperbolic surface
• Measurable Chromatic Number of Spheres