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