##
**Zentralblatt MATH**

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

**Zbl.No: ** 151.33204

**Autor: ** Erdös, Pál; Harary, Frank; Tutte, W.T.

**Title: ** On the dimension of a graph (In English)

**Source: ** Mathematika, London 12, 118-122 (1965).

**Review: ** The following concept of the dimension of a graph is presented: The dimension G of a graph G is the minimum number n such that G can be embedded into Euclidean n-space E_{n} with every edge of G having length 1. Some of the results: For the complete graph K_{m} with m vertices **dim** K_{m} = m-1; for the complete bicoloured graph K_{m,n}, **dim** K_{m,n} \leq 4, for n-dimensional cube Q_{n}, n > 1, is dim Q_{n} = 2 for all n. For any graph G with chromatic number \chi(G), **dim** G \leq 2 · \chi(G).

If **dim** G = 2, then \chi(G) \leq 7. Among all graphs with n vertices, q edges, and dimension 2k or 2k+1, **lim**_{n ––> oo} **max** qn^{-2} = ^{1}/_{2} (1-k^{-1}). Among any n points of E_{4} the distance 1 between pairs of points can occur at most n+[n^{2}/4] times, and this number can be realized if n \equiv 0 (mod 8).

**Reviewer: ** E.Jucovic

**Classif.: ** * 05C35 Extremal problems (graph theory)

05C15 Chromatic theory of graphs and maps

05C10 Topological graph theory

**Index Words: ** topology

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag