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\subseteqEh, where Eh 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 Eh is defined as \chie(Eh) = {t| G(U) can be made t-chromatic by deleting o(|S|2) edges, and U is finite}. The following bounds for \chie(Eh) are given: 1. \chie(Eh) \leq 2, 2. \chie(Eh) \geq h-2 for h \geq 2, 3. \chi(Sh-1) \leq \chie(E2h) \leq \chie(E2h+1) \leq \chi(Sh), where \chi(Sh-1) is the ordinary chromatic number of the sphere Sh-1 of radius 1/\sqrt2 in Eh. Furthermore, it is shown that for h \geq 2 the essential chromatic number of Eh coincides with the orthogonal chromatic number of Eh which is defined by: Given a set \Cal P of 2-dimensional subspaces of Eh, 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(Eh) = max{\chi(G(\Cal P))|\Cal P is finite}. Further results in this paper deal with embeddings of finite graphs in Eh. The dimension of a finite graph G is defined as dim(G) = max{h| G is contained in G(U) as a subgraph, U\subseteqEh is finite}; the faithful dimension of G is Dim(G) = max{h| G is isomorphic to G(U), U\subseteqEh 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