##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 466.05031

**Autor: ** Erdös, Paul; Simonovits, M.

**Title: ** On the chromatic number of geometric graphs. (In English)

**Source: ** Ars Comb. 9, 229-246 (1980).

**Review: ** In this paper, serveral kinds of geometric graphs which can be associated to a metric space U with metric \rho are studied for the case U\subseteq**E**^{h}, where **E**^{h} is the h-dimensional euclidean space. Let G(U) be the graph with vertex set U and which has as edge set the set of all pairs x,y in S with \rho(x,y) = 1, then the essential chromatic number of **E**^{h} is defined as \chi_{e}(**E**^{h}) = **{**t| G(U) can be made t-chromatic by deleting o(|S|^{2}) edges, and U is finite**}**. The following bounds for \chi_{e}(**E**^{h}) are given: 1. \chi_{e}(**E**^{h}) \leq 2, 2. \chi_{e}(**E**^{h}) \geq h-2 for h \geq 2, 3. \chi(S^{h-1}) \leq \chi_{e}(**E**^{2h}) \leq \chi_{e}(**E**^{2h+1}) \leq \chi(S^{h}), where \chi(S^{h-1}) is the ordinary chromatic number of the sphere S^{h-1} of radius 1/\sqrt2 in **E**^{h}. Furthermore, it is shown that for h \geq 2 the essential chromatic number of **E**^{h} coincides with the orthogonal chromatic number of **E**^{h} which is defined by: Given a set \Cal P of 2-dimensional subspaces of **E**^{h}, let \hat G(\Cal P) be the graph with vertex set \Cal P and which has as edge set the set of all pairs P,Q in \Cal P with P\perp Q, then the orthogonal number is \chi_{\perp}(**E**^{h}) = **max****{**\chi(G(\Cal P))|\Cal P is finite**}**. Further results in this paper deal with embeddings of finite graphs in **E**^{h}. The dimension of a finite graph G is defined as **dim**(G) = **max****{**h| G is contained in G(U) as a subgraph, U\subseteq**E**^{h} is finite**}**; the faithful dimension of G is Dim(G) = **max****{**h| G is isomorphic to G(U), U\subseteq**E**^{h} is finite**}**. These parameters are related to the maximum valence \Delta(G) of G by: 4. **dim**(G) \leq \Delta(G)+2, 5. Dim(G) \leq 2\Delta(G)+1.

**Reviewer: ** M.Walter

**Classif.: ** * 05C15 Chromatic theory of graphs and maps

05C10 Topological graph theory

**Keywords: ** geometric graphs; essential chromatic number; dimension of a graph

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag