Department of
Applied
Mathematics

The odd-distance graph

Moshe Rosenfeld

Abstract

A Geometric graph G(V,D) is a graph whose vertices V form a subset of a metric space M and D is a set of positive real numbers. Two vertices u and v are connected by an edge if d(u,v) belongs to D.

Probably the most famous geometric graph is G(R^2,{1}), the unit-distance graph. In 1994 I asked Paul Erdős whether what seemed like a closely related graph, the odd distance graph, has a finite chromatic number. And thus started the journey of the odd-distance graph. In this talk I will discuss some examples of geometric graphs and highlight related open problems. In particular, I will discuss recent new results on the odd-distance graph G(R^2, {1,3,5,...}). The latest, we proved that every finite 3-colorable graph can be faithfully embedded in the odd distance graph. This raises some interesting questions regarding faithfully embedding infinite graphs whose finite subgraphs can be faithfully embedded in the odd-distance graph.