Bollobas, B. and H.R. Hind, Graphs without large triangle free subgraphs, Discrete Mathematics 87 (1991) 119-131.
The main aim of the paper is to show that for 2 < r <s and large enough n, there are graphs of order n and clique number less than s in which every set of vertices, which is not too small, spans a clique of order r. Our results extend those of Erd& and Rogers.
Consider the set of graphs of order n not containing a K", a complete graph of order s, as a vertex induced subgraph. What is the maximum number of vertices, fr,s(n), such that any graph in our set contains a vertex induced subgraph of order fr,S(n) not containing a K' as a vertex induced subgraph?
This problem, which is essentially a problem of Ramsey Theory, was first considered by Erdiis and Rogers [5] in 1961, when they showed that there exist graphs of order n, not containing a K", such that every vertex induced subgraph of order more than r~'-~~", contains a KS-'. The value of l s obtained was E -1/(512s4 logs) for large values of S. The main aim of this paper is to improve this result.
The notation used will be standard (see [l]) and as is customary, the symbols C, Ct, Cl, . . . will be used to denote constants. Most of our proofs will make use of the theory of random graphs; for an introduction to the subject see [2].
For a given graph G, define h,(G) = max{lWI:
That is to say, h,(G) is the order of the largest subset of V(G) for which the corresponding vertex-induced subgraph of G does not contain a K'. For 2 s r < s * Supported by ORS grant ORS/84120 and CSIR grant 9/8/l-2019.