Coloring distance graphs: a few answers and many questions

Geombinatorics XXIV-3 (2015) p.117-134.

Article en pdf

Étant donné un espace métrique X et un ensemble de nombres positifs D, on peut former un graphe dont les sommets sont les éléments de X et où des arêtes relient préciséments les paires de points dont la distance appartient à D. Déterminer le nombre chromatique de ce graphe quand X est le plan euclidien et D est réduit à {1} est un problème classique et toujours ouvert.

Dans cet article, je considère plusieurs variations sur ce thème, en considérant notamment les distances sur 2 qui définissent la topologie usuelle et sont invariantes par translation (cadre dans lequel je réponds à des questions de Johnson et Szlam), et le plan hyperbolique.