Coloring The Line

Abstract

The distance graph \(G(S, D)\) has vertex set \(V(G(S, D)) = S \cup \mathbb{R}^n\) and two vertices \(u\) and \(v\) are adjacent if and only if their distance \(d(u, v)\) is an element of the distance set \(D \subseteq \mathbb{R}_+\).

We determine the chromatic index, the choice index, the total chromatic number and the total choice number of all distance graphs \(G(\mathbb{R}, D)\), \(G(\mathbb{Q}, D)\) and \(G(\mathbb{Z}, D)\) transferring a theorem of de Bruijn and Erdős on infinite graphs. Moreover, we prove that \(|D| + 1\) is an upper bound for the chromatic number and the choice number of \(G(S,D)\), \(S \subseteq \mathbb{R}\).