## 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