##
**Zentralblatt MATH**

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

**Zbl.No: ** 125.40501

**Autor: ** Erdös, Pál; Hajnal, András

**Title: ** On complete topological subgraphs of certain graphs (In English)

**Source: ** Ann. Univ. Sci. Budapest. Rolando Eötvös, Sect. Math. 7, 143-149 (1964).

**Review: ** Let G(n,l) a graph of n vertices and l edges. We say that G(n,l) contains a complete k-gon if there are k vertices of G(n,l) any two of which are connected by an edge, we say that it contains a complete topological k-gon if it contains k vertices any two of which are connected by paths no two of which have a common vertex (except of endpoints). Denote the complete k-gon by < k> , and the complete topological k-gon by < k> , and the complete topological k-gon by < k>_{t}. The first theorem of the paper is the following: If r \geq 2 and c_{3} \geq 1/(2r+2), then G(n,c_{3}n^{2}) contains < [c_{4} n^{1/r} ]>_{t}, where c_{4} depends on c_{3}. Denote by f(k,l) the smallest integer such that splitting the edges of an < f(k,l)> into two classes in an arbitrary way, either the first contains a < k> or the second an < l> . There are estimation for f(k,l). [*P. Erdös* and *G. Szekeres*, Zbl 012.27010; *C. Frasney*, C. R. Acad. Sci., Paris 256, 2507-2510 (1963; Zbl 211.02502); *P. Erdös*, Zbl 032.19203; Zbl 097.39102) Similarly, denote by f(k_{t},l_{t}) the smallest integer such that splitting the edges of an < f(k_{t}l_{t})> into two classes in an arbitrary way, either the first contains a < k>_{t} or the second an < l>_{t}. Moreover f(k,l_{t}) and f(k_{t},l) have a self-explanatory meaning. Theorem 2. gives the estimations c_{1} k^{2} < f(k_{t}l_{t}) < c_{2}k^{2},

c_{5}l^{4/3}(log l)^{-3/2} < f(3,l_{t}) \leq {l+1 \choose 2},

c_{6}k^{3}(log k)^{-1} < f(k,k_{t}). The symbol m ––> oo (m_{t},m_{t})^{2} denotes the statement that if we split the edges of a complete graph of power m into two classes in an arbitrary way, then there exists a complete topological subgraph of power m all whose edges belong to the same class. The third theorem states m ––> (m_{t},m_{t})^{2} if m is an arbitrary cardinal. The paper contains further interesting results as collararies to the main theorems, and unsolved problems.

**Reviewer: ** Gy.Katona

**Classif.: ** * 05C10 Topological graph theory

**Index Words: ** topology

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag