##
**Zentralblatt MATH**

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

**Zbl.No: ** 596.05027

**Autor: ** El-Zahar, M.; Erdös, Paul

**Title: ** On the existence of two non-neighboring subgraphs in a graph. (In English)

**Source: ** Combinatorica 5, 295-300 (1985).

**Review: ** There is raised the following question: Is there a minimal integer f(r,n) such that each graph G with \chi(G) \geq f(r,n) and which does not contain a complete subgraph of order r must contain two non-neighboring n-chromatic subgraphs? It is known that f(r,2) exists. There is shown that for a fixed n, an upper bound for f(r,n), r > n is given in terms of f(r,n), r \leq n. From f(3,3) \leq 8 is deduced an upper bound for f(r,3) and proved that a vertex critical 4-chromatic graph which does not contain two independent edges has order \leq 13.

**Reviewer: ** J.Fiamcik

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

05C35 Extremal problems (graph theory)

**Keywords: ** non-neighboring n-chromatic subgraphs

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag